Doubly Linked List

Doubly Linked Lists:

Doubly Linked Lists CS 308 – Data Structures

Node data :

Node data info : the user's data next, back : the address of the next and previous node in the list .back .next .info

Node data (cont.):

Node data (cont.) template<class ItemType> struct NodeType { ItemType info; NodeType<ItemType>* next; NodeType<ItemType>* back; };

Finding a List Item :

Finding a List Item We no longer need to use prevLocation (we can get the predecessor of a node using its back member)

Finding a List Item (cont.):

Finding a List Item (cont.)

Inserting into a Doubly Linked List :

Inserting into a Doubly Linked List 1. newNode->back = location->back; 3. location->back->next=newNode; 2. newNode->next = location 4. location->back = newNode;

FindItem(listData, item, location, found):

FindItem(listData, item, location, found) RetrieveItem , InsertItem , and DeleteItem all require a search ! Write a general non-member function FindItem that takes item as a parameter and returns location and found . InsertItem and DeleteItem need location (ignore found ) RetrieveItem needs found ( ignores location)

Finding a List Item (cont.):

Finding a List Item (cont.) template<class ItemType> void FindItem(NodeType<ItemType>* listData, ItemType item, NodeType<ItemType>* &location, bool &found) { // precondition: list is not empty bool moreToSearch = true; location = listData; found = false; while( moreToSearch && !found) { if(item < location->info) moreToSearch = false; else if(item == location->info) found = true; else { if(location->next == NULL) moreToSearch = false; else location = location->next; } } }

How can we distinguish between the following two cases?:

How can we distinguish between the following two cases?

Special case: inserting in the beginning:

Special case: inserting in the beginning

Inserting into a Doubly Linked List:

Inserting into a Doubly Linked List template<class ItemType> void SortedType<ItemType>::InsertItem(ItemType item) { NodeType<ItemType>* newNode; NodeType<ItemType>* location; bool found; newNode = new NodeType<ItemType>; newNode->info = item; if (listData != NULL) { FindItem(listData, item, location, found); if (location->info > item) { newNode->back = location->back; newNode->next = location; if (location != listData) // special case (location->back)->next = newNode; else listData = newNode; location->back = newNode; } (1) (2) (3) (4) (3)

Inserting into a Doubly Linked List (cont.):

Inserting into a Doubly Linked List (cont.) else { // insert at the end newNode->back = location; location->next = newNode; newNode->next = NULL; } } else { // insert into an empty list listData = newNode; newNode->next = NULL; newNode->back = NULL; } length++; }

Deleting from a Doubly Linked List :

Deleting from a Doubly Linked List Be careful about the end cases!!

Headers and Trailers:

Headers and Trailers Special cases arise when we are dealing with the first or last nodes How can we simplify the implementation? Idea : make sure that we never insert or delete the ends of the list How ? Set up dummy nodes with values outside of the range of possible values

Headers and Trailers (cont.):

Headers and Trailers (cont.) Header Node : contains a value smaller than any possible list element Trailer Node : contains a value larger than any possible list element

A linked list as an array of records:

A linked list as an array of records What are the advantages of using linked lists? (1) Dynamic memory allocation (2) Efficient insertion-deletion (for sorted lists) Can we implement a linked list without dynamic memory allocation ?

A linked list as an array of records (cont.):

A linked list as an array of records (cont.)

Case Study: Implementing a large integer ADT :

Case Study: Implementing a large integer ADT The range of integer values varies from one computer to another For long integers, the range is [-2,147,483,648 to 2,147,483,647] How can we manipulate larger integers?

Case Study: Implementing a large integer ADT (cont.):

Case Study: Implementing a large integer ADT (cont.) - A special list ADT

Exercises:

Exercises 1, 6, 8, 10, 12