How do links work
See my notes
[ linked.html ]
and
[ pointers.html ]
Resources on Linked data structures and linked lists
The Wikipedia
[ Linked_lists ]
has a pretty standard introduction plus the history.
and
[ linkedlists.html ]
gives personal view of this material. The US National
Institute of Standards and Technology
[ linkedList.html ]
(NIST) has a one page description with links to related items and demos.
Review how simple pointers work
[ 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:
class ForExample{
ForExample * i_am_a_link;
ForExample i_am_a_mistake;
};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
[ 15demo.cpp ]
is a
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.
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
[ ../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 [ 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
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:
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 [ Tree_sort ] has a good description. Here is quick C++ [ 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
[ 17.html ]
Project 4 and Quiz 4 next time
Abbreviations