.Open CSci202 Computer Science II, Session 16 Linked Data Structures (previous): Searching and Sorting .See http://www/dick/cs202/15.html . Preparation -- 20 Data Structures 945 20.1 Introduction 946 20.2 Self-Referential Classes 947 20.3 Dynamic Memory Allocation and Data Structures 948 20.4 Linked Lists 948 20.5 Stacks 963 20.6 Queues 968 SKIP 20.7 Trees 972 (Trees will be covered in CSci330) 20.8 Wrap-Up 980 . How do links work See my notes .See ./linked.html and .See ./pointers.html . Resources on Linked data structures and linked lists The Wikipedia .See http://en.wikipedia.org/wiki/Linked_lists has a pretty standard introduction plus the history. and .See http://www.inversereality.org/tutorials/c++/linkedlists.html gives personal view of this material. The US National Institute of Standards and Technology .See http://www.itl.nist.gov/div897/sqg/dads/HTML/linkedList.html (NIST) has a one page description with links to related items and demos. . Review how simple pointers work .See ./12program.html . What is "dynamic memory", and how important is it Dynamic memory is in a part of RAM called "the heap". The program can ask for more data any time it wants, and keep it until it doesn'e need it. It can then be recycled. This is why it is called "dynamic". Normal variables are on the run time stack. It is a Stack -- Last In First Out. Your program can not keep a variable and use it after it leaves the block. A lot of problems demand the use of an unknown amount of data -- and this is what dynamic memory is for. If you can only use a fixed amount (fixed at compile time) then your program is stopped from handling anything but problems that are handled by a "Finite State Machine". For example.... read in a string of unknown length and determine if it is a palindrome. This needs an unknown amount of memory -- and that means at least a stack. . What is a Link? (link): A link is a field/attribute/data member in an object that points at another object. In linked lists and trees links point at objects of the same type: .As_is class ForExample{ .As_is ForExample * i_am_a_link; .As_is ForExample i_am_a_mistake; .As_is }; Linked data structures are constructed out of Elements or Nodes. Typically Nodes/Elements they contain some data plus some links. Elements and Nodes often have a constructor that is used by another class -- the Data Structure or Container to organize them. Sometimes the Node class is a private class inside the Container. Because the Nodes are hidden we can allow their contents to be public -- and so available to the containing structure. Another technique is for the Node to be public, have private members but declare the Container as a friend. Finally, the Node can define pubic operations that enable the container to manipulate the node. This is risky because it lets any part of the program do the same thing. And the other parts of the program may be written by someone who doesn't know what they are doing. Here .See http://www/dick/cs202/15demo.cpp is a .Key demonstration of how links work that shows you the numerical values of each link and the addresses of the nodes in a list. . Which data structures are the easiest to use, which are the most difficult Vectors are easier than arrays, arrays easier than Do-It-Yourself linked lists. Just about any data structure in the library is easier to use than one that you do for yourself. . Do certain data structures work better with certain algorithms than others Yes. . When should I use linked data .List When you have data that needs inserting, deleting, and/or moving at random. When data is moved more often than it is looked up. When there are links in the real world. For example a simple library .See http://www/dick/cs202/library.cpp or a complex family tree .See http://www/dick/cs202/family.cpp program. After you've sketched a UML class diagram with several linked classes. .Close.List . What are the ideal uses for linked lists The original purpose was to represent data in Artificial Intelligence. All Operating Systems and Compilers use linked data structures. In a sense the World Wide Web is a massive linked data structure. . How do I show links in the UML? For a single link use a simple arrow ("---->") connecting from the class that has the pointer to the class that is pointed at. If their are pointers in both directions (as in a doubly linked list) omit the arrow. For more see .See ../samples/uml1b.html#Linked Data Structures . Can you give a few examples for the uses of the data lists from the book I plan to walk through an example or two on the board with faked values for the pointers. . Chapter 20 pages 947-949 -- Data structure What are data structure and what are they used for? A collection of items connected together by their position and/or by links. The items are called nodes. The data structure is sometimes called a container. . Chapter 20 pages 947 -- Self Referential Classes Can you re-explain what self referential class does and give an example of it? A "self-referential class" is a class that has a link to an object that is an instance of the same class. For example a person may have a link to their father who is another person. A each item in a list has a link to the `next` item (if any) in the list. . Can you give an example of self-referential class objects linked together Produces a chain of paper clips from bag.... Drops keys on floor.... This .See http://www/dick/cs202/15demo.cpp example is a self-referential class .... UML drawn on board. The queue of print jobs for the printer in JBH359. Here is an example of a linked list that I wish I had: link all the CS202 question on my Email together so I can click through them and give points to the people who sent them. How about a collection of people and we link each person to their closest friend? Notice a single link points to one object so we can not use a simple link between friends.... one person can have many friends. To handle this.... we have to create a data structure that holds a Person's friends. Seeing that friendship changes... UML sketch on board of People and SetOfFriends classes. Suppose we are interested in modeling the stress inside a large container of chemicals. 20 foot high.... I calculated the stresses on a nice simple shape: A cylinder with a hemispherical dome on top in 1966.... but suppose it is a complex shape. Then we would split the shell into a collection of finite elements and link each one to the ones next to it. How about the spread of swine flu... . in the example in 20.2 what would be the next object pointed at if nothing is specified Who knows. Could be any random part of the computer, probably a bug! This is one of the things that your links must never be allowed to do. . Why Does the linked list implementation use templates Exercise for class.... why not rewrite the code each time you want a new list with different data? . How do memory leaks occur When data is allocated on the heap with `new` but is not given back for recycling with a `delete` command. . what are common mistakes when doing stacks Trying to pop the stack when it is empty. . What are the primary function of stacks and why Stacks have many uses. The two famous ones are .List Reversing incoming data -- it works. Compiling expressions -- it works! Burrough's Computer Corp 1960's Evaluating expressions -- it works! .Close.List You can add to these that is the simplest linked list container and so useful for quick and dirty solutions to problems that make you to store an unknown number of data items. I can remember solving a bug inside a Prolog interpreter by defining a very simple stack, pushing the items into it, if they weren't already there, and then popping them off the stack and deleting them... I was working in C with no STL. I figured that I didn't have time to create an efficient data structure (some kind of balanced tree) before the laboratory. . Which data structure is more commonly used Stacks or Queues and can you show an example of each Both are used a lot. You find queues in operating systems and stacks in compilers. Queues often turn up in simulations. Stacks in interpreters and work with languages. You need to be ready to use either one depending on what behavior you need in the program: .List LIFO -- Last In First Out FIFO -- First In First Out .Close.List . Can you further explain Stacks and Queues and how they differ from Trees Stacks and queues a simpler. Trees are more complex. Stacks and queues are linear, trees branch out. In a stack or Queue each item has at most one before it and at most one after it. In a tree, each item has at most one above it (the parent) but can have any number underneath it (children). Stacks and queues have two ends. A tree has one root and any number of leaves. . Are binary trees useful Yes. A fair chunk of CSCI330 is all about binary trees. In CSCI320 we talk about a language (LISP) that stores all its data in binary trees. As a general rule.... they can do anything that a linked list can do in O(`n`) in O(log(`n`)). . Can you give us an example on what we would use a binary tree for In this class they won't be needed. There is an elegant sort -- TreeSort -- that uses trees. It has the same performance as QuickSort. We don't have time to study it in CS202. The Wikipedia .See http://en.wikipedia.org/wiki/Tree_sort has a good description. Here is quick C++ .See ./treesort.cpp version. Inside the STL are several containers (set, multiset, map, multimap) that have binary trees inside them. . What is the point, or purpose, of fig. 20.20-20.22 To give you a simple (simple!) example of a binary search tree and the three standard ways of visiting every part of the tree. More in CS330. . Next -- Bits and Pieces .See ./17.html . Project 4 and Quiz 4 next time