(previous): Linked Data Structures [ 15.html ]

Preparation

Study this page and chapter 13, sections 13.1 and 13.2 ONLY.

Error on page 482

This

 		c=s.pop();

is wrong and should be

 		c=s.top();

 		s.pop();

(Once we normally defined "pop()" to return a copy of the top of the stack, but no longer... and Scansholm forgot to update his code on this page...

Assigned Work Due

Hand in your questions, doubts and surprises.

Input

How do links work

See my notes [ linked.html ] and [ pointers.html ]

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 they 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.... and are hidden inside another class that defines how to place data in the structure and how to extract it afterward. Because the Nodes are kept private we can allow their contents to be public -- and so available to the containing structure.

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. This follows the example in the book.

When should I use linked data



1. When you have data that needs inserting, deleting, and/or moving at random.
2. When there are links in the real world for example a simple library [ library.cpp ] or a more complex family tree [ family.cpp ] program.
3. After you've sketched a UML class diagram with several linked classes.



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 ]

Book Topics

13.1 Linked Lists: the Basics

1. 13.1.2 Singly linked lists
   
   1. Building up a list
   2. Running through a list
   3. Putting elements into a list and removing them
   4. Linked lists and recursion
   
   
2. 13.1.2 Doubly Linked Lists

   13.2 Linked lists: Applications

3. 13.2.1 Stacks: Good for evaluating expressions and reversing sequences.
4. 13.2.2 Queues: Good when things must wait, but be processed in the same sequence, and for simulations.
5. 13.2.3 Sets: Good when you want to know if something has been seen before and don't want multiple copies. Note: the stl provides a faster implementation.

   Here [ Set.png ] is a UML diagram of the books Set and Element classes ( download model from [ Set.dia ] ).

. . . . . . . . . ( end of section Book Topics) <<Contents | End>>

Questions

What are double linked lists?

A single linked list has one link. A double linked list has two paired links. One reverses the other. So, if one is "next" and the other is "previous" then we expect

 		pointer->next->previous == pointer

whenever pointer->next is not NULL.

See pages 475...

Can you go over recursive data types?

Data types are not exactly recursive. They just can store the addresses of objects of the same type. This lets them reflect a recursive structure in the real world. For example in a family tree each person has two parents, so a realistic class would be:

 		class Person{

 		...

 			Person * mother;

 			Person * father;

 		...

			friend void print_ancestors(Person * p, int gen);

 		...

 		};

The rule is that once the compiler sees "class NNN" then you can declare pointers "NNN * nnn;". The NNN class is incomplete. You can not declare objects of type NNN: "NNN object" until the complete class is done.

We use can use recursion to move around and explore these structures:

		void Person::print_ancestors(Person *p, int g=0)

 		{

 			if(p)

 			{

 				list_ancestors(p->mother, g+1);

 				list_ancestors(p->father, g+1);

 				cout << substr(".........", 0, g)<<*p<<endl;

 			}

 		}

(unchecked code).

What is the advantage of a list over a vector?

You can quickly insert and delete items into the middle of a list.

How can items be inserted in alist without moving the other items out of the way?

In a linked list items are not stored in a sequence of adjacent pieces of memory -- like an array or a vector. They are placed where-ever their is space in the computer. The sequence is maintained by the computer remembering where the data has been put. So if we have two chars 'a' and 'b' in the first and last elements of a linked list the memory could look like this:

Address	Contents	Symbol in C++
...
1200	'b'	first->next
1202	0	first->next->next
1202	2400	first->next->prev
...
2400	'a'	first
2401	1200	first->next
2402	0	first->prev
...

We would also need to store the number 2400 as the address of the first item. Now when we insert data 'c' in between 'a' and 'b' we could get

Address	Contents
...
1200	'b'
1202	0
1202	3400
...
2400	'a'	first
2401	3400
2402	0
...
3400	'c'
3401	1200
3402	2400
...

Notice that the data are in the same places but the pointer values have changed.

Is their something like Element hidden in the C++ Standard Library?

Probably. Just about every linked implementation of a container has an Element or Node internal (and private) class to hold the contained data and links to other items in the container. You might try the source code in /usr/include/g*/....

Are pointers stored in RAM?

Yes.

Do pointers use less bits?

Yes.

Because: a typical rcord for a person might have several 100 bits of data and the point no more than 32bits.

Consider: which takes up more space:

		QA76.76 C 1978

or the book found at that place on the shelves in the library.

Which takes up more space: you or your phone number?

Why combine linked data structures and recursion to reverse a string?

Why not? It is easy! You can also use a stack..... see the text and laboratory 8 below.

15demo.cpp didnt work on MicroSoft.NET

I'm not surprised.... I would guess you will have to do something with <iostream> and cerr. Let me know more detials... TBD

What is a set?

In mathematics it is an unordered collection of elements with no repeats. In Computer Science it is an ordered set of items. We have at least the following operations

Name	Math	Meaning
member	x ∈ A	True if x is in A else false.
union	A ∪ B	Elements in either A or B
intersection	A ∩ B	Elements in both A and B
insert	-	Afterward inserted element is in set
remove	-	Afterward inserted element is not in set

Can you explain the helper function uni?

This is a classic two way merge of two sorted lists. It works by selecting the smallest of the first items in the two lists. For example merging (1,3,4) and (2,3,5) we create a list that starts (1.... and is followed by the merge of (3,4) and (2,3,5). To merge (3,4) and (2,3,5) we take the 2 and then merge (3,4) and (3,5). Then we get the 3 and add to it the merge of (4) and (5). We have to be careful at the end of lists.... but we will get ...4,5). Putting these parts together gives us (1,2,3,4,5).

You can always type in code like this and add a debugging output:

 		cerr<< .....<< endl;

at the start to see what the code does.

Doubly linked lists seem better than singly linked lists should we also use them?

Adding links to a data structure often makes it more powerful. However we have to store the extra pointer, and we have to manipulate/copy/change the extra pointer. As a result doubly linked lists take up more space and can be slower than singly linked lists.

Use a simply linked list when you need a simple structure and program performance is more important than your time. Otherwise use the Standard Library!

Use a doubly linked list when you want reliable coded and bi-directional access.

In a complex data structure with many different links use the UML to work out whther you need a single or double linked connection. An arrow head [ Linked Data Structures in uml1b ] is the best notation for singly linked data.

What is the special Element at the start of the Doubly Linked list in the book?

This is a called a tombstone. It stays there when the rest of the list has gone. It simplifies coding insertion and deletion because we know that before EVERY Element there is a previous one, and after each one there is a next Element. No NULL pointers to test for and program around.

What is the difference between a link and a pointer?

Not much. A link is often used to indicate a special pointer used to connect items in a container. So a link typically is a pointer from a class, back into the same class.

.

Why use a dynamically linked list instead of an array/vector/deque/...

To allow you to insert and delete elements in the middle, without copying the data.

Exercises

Depends on the questions!

. . . . . . . . . ( end of section CSci202 Computer Science II, Session 15 Linked Data Structures) <<Contents | End>>

Laboratory 8 Implementing and using a Stack to Evaluate Expressions

Abbreviations