Data Structures Using C++ 2E

Chapter 5
Linked Lists
 Objectives

• Learn about linked lists

• Become aware of the basic properties of linked lists
• Explore the insertion and deletion operations on
linked lists
• Discover how to build and manipulate a linked list

Data Structures Using C++ 2E 2

 Objectives (cont’d.)

• Learn how to construct a doubly linked list

• Discover how to use the STL container list
• Learn about linked lists with header and trailer
nodes
• Become aware of circular linked lists

Data Structures Using C++ 2E 3

 Linked Lists
• Collection of components (nodes)
– Every node (except last)
• Contains address of the next node
• Node components
– Data: stores relevant information
– Link: stores address
• Advantages
– No need to mention size
– FIGURE 5-1 Structure of a node
No space limitation
– No memory wastage
– Dynamic memory allocation
Data Structures Using C++ 2E 4
 Linked Lists (cont’d.)
• Head (first)
– Address of the first node in the list
• Arrow points to node address
– Stored in node
• Down arrow in last node indicates NULL link field

FIGURE 5-2 Linked list

FIGURE 5-3 Linked list and values of the links

Data Structures Using C++ 2E 5
 Linked Lists (cont’d.)

• Two node components

– Declared as a class or struct
• Data type depends on specific application
– Link component: pointer
• Data type of pointer variable: node type itself (self
referential)

Data Structures Using C++ 2E 6

 Linked Lists: Some Properties
• Head stores address of first node
• Info stores information
• Link stores address of next node
– Assume info type int

FIGURE 5-4 Linked list with four nodes

TABLE 5-1 Values of head and some of
the nodes of the linked list in Figure 5-4

Data Structures Using C++ 2E 7

Linked Lists: Some Properties (cont’d.)

• Pointer current: same type as pointer head

– current = head;
• Copies value of head into current
– current = current->link;
• Copies value of current->link (2800) into
current

FIGURE 5-5 List after the statement

current = current->link; executes

Data Structures Using C++ 2E 8

Linked Lists: Some Properties (cont’d.)

TABLE 5-2 Values of current, head, and

some of the nodes of the linked list in Figure 5-5

Data Structures Using C++ 2E 9

 Traversing a Linked List

• Basic linked list operations

– Search list to determine if particular item is in the list
– Insert item in list
– Delete item from list
• These operations require list traversal
– Given pointer to list first node, we must step through
list nodes

Data Structures Using C++ 2E 10

 Traversing a Linked List (cont’d.)

• Suppose head points to a linked list of numbers

– Code outputting data stored in each node

Data Structures Using C++ 2E 11

 Item Insertion and Deletion
• Assuming the following

• While considering the following list

Data Structures Using C++ 2E 12

 Item Insertion and Deletion
TABLE 5-3 Inserting a node in a linked list

Data Structures Using C++ 2E 13

 Item Insertion and Deletion (cont’d.)

• Sequence of statements to insert node is

– Very important
• Use only one pointer (p) to adjust links of the nodes
• See next slide

Data Structures Using C++ 2E 14

 Item Insertion and Deletion (cont’d.)

Data Structures Using C++ 2E 15

 Item Insertion and Deletion (cont’d.)
• Using two pointers can simplify insertion code somewhat

Data Structures Using C++ 2E 16

 Item Insertion and Deletion (cont’d.)
– Deleting a node pointed to by p.
– Steps

FIGURE 5-10 List after the statement

p->link = p->link->link; executes

The node with info 34 is removed from the list.

However, the memory is still occupied by this node and this memory
is inaccessible
Data Structures Using C++ 2E 17
 Item Insertion and Deletion (cont’d.)
• To deallocate the memory, we need a pointer to this
node.
• The following statements delete the node from the list
and deallocate the memory occupied by this node:

Data Structures Using C++ 2E 18

 Building a Simple Linked List

Data Structures Using C++ 2E 19

Building a Simple Linked List

Data Structures Using C++ 2E 20

Building a Simple Linked List

Data Structures Using C++ 2E 21

Building a Simple Linked List

Data Structures Using C++ 2E 22

Building a Simple Linked List

Output

Data Structures Using C++ 2E 23

 Building a Linked List
• Ways to build linked list
– Forward
• New node always inserted at end of the linked list
• See example on page 274
• See function buildListForward on page 277

– Backward
• New node always inserted at the beginning of the list
• See example on page 277
• See function buildListBackward on page 278

Data Structures Using C++ 2E 24

 Input: 2 15 8 24 34 -999

Data Structures Using C++ 2E 25

 Input: 2 15 8 24 34 -999

Data Structures Using C++ 2E 26

 Linked List as an ADT

• 11 basic operations
• Two types of linked lists: sorted and unsorted
• class linkedListType
– Implements basic linked list operations as an ADT
– Derive two classes using inheritance
• unorderedLinkedList and orderedLinkedList
• Unordered linked list functions
– buildListForward and buildListBackward
– Two more functions accommodate both operations
• insertFirst and insertLast

Data Structures Using C++ 2E 27

Data Structures Using C++ 2E 28
 Structure of Linked List Nodes

• Node has two instance variables

– Simplify operations (insert, delete)
• Define class to implement linked list node as a struct
• Definition of the struct nodeType

Data Structures Using C++ 2E 29

 Member Variables of the class
linkedListType
• class linkedListType
– Three instance variables

Data Structures Using C++ 2E 30

 Linked List Iterators [SKIPPED]

• To process each node

– Must traverse list starting at first node
• Iterator Object producing each element of a
container
– One element at a time
• Operations on iterators: ++ and *
• See code on pages 280-281
– class linkedListType
– Functions of class linkedListIterator

Data Structures Using C++ 2E 31

 linkedListIterator [SKIPPED]

Data Structures Using C++ 2E 32

 Linked List Type

• Abstract class linkedListType Why?

– Defines basic properties of a linked list as an ADT
– See code on page 282

Data Structures Using C++ 2E 33

 Linked List as an ADT (cont’d.)
• Default constructor and isEmptyList()

Data Structures Using C++ 2E 34

 Linked List as an ADT (cont’d.)
• Destroy the list
– Deallocates memory occupied by each node

template <class Type>

void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp; //pointer to deallocate the memory
//occupied by the node
while (first != NULL) //while there are nodes in the list
{
temp = first; //set temp to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate the memory occupied by temp
}
last = NULL; //initialize last to NULL
count = 0;
}

Data Structures Using C++ 2E 35

 Linked List as an ADT (cont’d.)
• Initialize the list
– Reinitializes list to an empty state
• Must delete the nodes (if any) from the list

Data Structures Using C++ 2E 36

 Linked List as an ADT (cont’d.)
• Print the list
– Must traverse the list starting at first node

Data Structures Using C++ 2E 37

 Linked List as an ADT (cont’d.)
• Length of a list
– Number of nodes stored in the variable count
– Function length
• Returns value of variable count

Data Structures Using C++ 2E 38

 Linked List as an ADT (cont’d.)
• Retrieve the data of the first and last node

Data Structures Using C++ 2E 39

 Linked List as an ADT (cont’d.)

• Copy the list

– Makes an identical copy of a linked list
• Create node called newNode
• Copy node info (original list) into a newNode
• Insert newNode at the end of list being created
– See function copyList on page 289

Data Structures Using C++ 2E 40

Data Structures Using C++ 2E 41
 Linked List as an ADT (cont’d.)

• Destructor
– When class object goes out of scope
• Deallocates memory occupied by list nodes
– Memory allocated dynamically
• Resetting pointers first and last
– Does not deallocate memory
– Must traverse list starting at first node
• Delete each node in the list
– Calling destroyList() destroys the list

Data Structures Using C++ 2E 42

 Linked List as an ADT (cont’d.)

• Copy constructor
– Makes identical copy of the linked list
– Function copyList checks whether original list
empty
• Checks value of first
– Must initialize first to NULL
• Before calling the function copyList
• Overloading the assignment operator
– Similar to copy constructor definition

Data Structures Using C++ 2E 43

 TABLE 5-6 Time-complexity of the operations of the
class linkedListType

Data Structures Using C++ 2E 44

 Unordered Linked Lists

• Derive class unorderedLinkedList from the

abstract class linkedListType
– Implement the operations search, insertFirst,
insertLast, deleteNode
• See code on page 292
– Defines an unordered linked list as an ADT
– class unorderedLinkedList

Data Structures Using C++ 2E 45

 Unordered Linked Lists

Data Structures Using C++ 2E 46

 Unordered Linked Lists (cont’d.)

• Search the list

– Steps
• Step one: Compare the search item with the current
node in the list. If the info of the current node is the
same as the search item, stop the search; otherwise,
make the next node the current node
• Step two: Repeat Step one until either the item is found
or no more data is left in the list to compare with the
search item
– See function search on page 293

Data Structures Using C++ 2E 47

 Unordered Linked Lists (cont’d.)

Data Structures Using C++ 2E 48

 Unordered Linked Lists (cont’d.)

• Insert the first node

– Steps
• Create a new node
• If unable to create the node, terminate the program
• Store the new item in the new node
• Insert the node before first
• Increment count by one
– See function insertFirst on page 294
– We covered this idea in BuildListBackward()

Data Structures Using C++ 2E 49

 Unordered Linked Lists (cont’d.)

• Insert the last node

– Similar to definition of member function
insertFirst
– Insert new node after last
– See function insertLast on page 294

– We covered this idea in BuildListForward() and

insertLast()

Data Structures Using C++ 2E 50

 Delete a node
• Consider the following cases:
1. The list is empty
2. The list is nonempty and the node to be deleted is the first
node
a) If this was the only node, then empty the list
b) Otherwise, the second node will be become the first one.
3. The list is nonempty and the node to be deleted is not the first
node, it is somewhere in the list
a) The node to be deleted is NOT the last node
b) The node to be deleted is the last node
4. The node to be deleted is not in the list

• See pseudocode on page 295

• See definition of function deleteNode on page 297
Data Structures Using C++ 2E 51
template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1; the list is empty.
cout << "Cannot delete from an empty list."<< endl;
else
{
if (first->info == deleteItem) //Case 2
{
current = first;
first = first->link;
count--;
if (first == NULL) //if this was the only node
last = NULL; // empty the list
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //current is one step ahead
current = first->link; of trailcurrent

Data Structures Using C++ 2E 52

 while (current != NULL && !found)
{
if (current->info != deleteItem)
{
trailCurrent = current;
current = current-> link;
}
else
found = true;
}//end while
if (found) //Case 3; if found, delete the node
{
trailCurrent->link = current->link;
count--;
if (last == current) //node to be deleted was the last
last = trailCurrent;
delete current; //delete the node from the list
}
else
cout << "The item to be deleted is not in the list.\n";

}//end else
}//end else
}//end deleteNode
Data Structures Using C++ 2E 53
 Unordered Linked Lists (cont’d.)
TABLE 5-7 Time-complexity of the operations of the
class unorderedLinkedList

Data Structures Using C++ 2E 54

 Header File of the Unordered Linked
List
• Create header file defining class
unorderedListType
– See class unorderedListType code on page
299
• Specifies members to implement basic properties of an
unordered linked list
• Derived from class linkedListType

Data Structures Using C++ 2E 55

 Ordered Linked Lists

• Derive class orderedLinkedList from class

linkedListType
– Provide definitions of the abstract functions:
• insertFirst, insertLast, search, deleteNode
– Ordered linked list elements are arranged using some
ordering criteria
• Assume elements of an ordered linked list arranged in
ascending order
• See class orderedLinkedList on pages 300-
301

Data Structures Using C++ 2E 56

 Ordered Linked Lists (cont’d.)

• Search the list

– Steps describing algorithm
• Step one: Compare the search item with the current
node in the list. If the info of the current node is greater
than or equal to the search item, stop the search;
otherwise, make the next node the current node
• Step two: Repeat Step one until either an item in the list
that is greater than or equal to the search item is found,
or no more data is left in the list to compare with the
search item
We have already covered this idea except the red text.

Data Structures Using C++ 2E 57

 Ordered Linked Lists (cont’d.)

• Insert a node
– Find place where new item goes
• Insert item in the list
– See code on page 304
• Definition of the function insert

Data Structures Using C++ 2E 58

 Ordered Linked Lists (cont’d.)
• Insert a node (cont’d.)
– Consider the following cases

Data Structures Using C++ 2E 59

 Insert a node

Example: insert 5 then 15

List: 10 20 30

Data Structures Using C++ 2E 60

//end of while
 Insert a node

//3b

//3a

Data Structures Using C++ 2E 61

 Ordered Linked Lists (cont’d.)

• Insert first and insert last

– Function insertFirst
• Inserts new item at beginning of the list
• Must be inserted at the proper place
– Function insertLast
• Inserts new item at the proper place

Data Structures Using C++ 2E 62

 Ordered Linked Lists (cont’d.)

• Delete a node
– Several cases to consider
– See function deleteNode code on page 306

Data Structures Using C++ 2E 63

 Ordered Linked Lists (cont’d.)

TABLE 5-8 Time-complexity of the operations of

the class orderedLinkedList

Data Structures Using C++ 2E 64

 Header File of the Ordered Linked List

• See code on page 308

– Specifies members to implement the basic properties
of an ordered linked list
– Derived from class linkedListType
• See test program on page 309
– Tests various operations on an ordered linked list

Data Structures Using C++ 2E 65

 Doubly Linked Lists
• Traversed in either direction
• Typical operations
– Initialize the list
– Destroy the list
– Determine if list empty
– Search list for a given item
– Insert an item
– Delete an item, and so on
• See code on page 311
– Class specifying members to implement properties of
an ordered doubly linked list
Data Structures Using C++ 2E 66
 Doubly Linked Lists (cont’d.)

• Linked list in which every node has a next pointer

and a back pointer
– Every node contains address of next node
• Except last node
– Every node contains address of previous node
• Except the first node

FIGURE 5-27 Doubly linked list

Data Structures Using C++ 2E 67

 Doubly Linked Lists (cont’d.)
• Default constructor

• isEmptyList

Data Structures Using C++ 2E 68

 Doubly Linked Lists (cont’d.)
• Destroy the list

Data Structures Using C++ 2E 69

 Doubly Linked Lists (cont’d.)
• Initialize the list

• Length of the list

Data Structures Using C++ 2E 70

 Doubly Linked Lists (cont’d.)
• Print the list: Traverse list starting from the first node
• Reverse print the list
• Traverse list starting from the last node

Data Structures Using C++ 2E 71

 Doubly Linked Lists (cont’d.)
• Search the list
– Function search returns true if searchItem found
• Otherwise, it returns false
– Same as ordered linked list search algorithm

• First and last elements

– Function front returns first list element
– Function back returns last list element
– If list empty
• Functions terminate the program

Data Structures Using C++ 2E 72

 Doubly Linked Lists (cont’d.)

• Insert a node
– Four cases
• Case 1: Insertion in an empty list
• Case 2: Insertion at the beginning of a nonempty list
• Case 3: Insertion at the end of a nonempty list
• Case 4: Insertion somewhere in a nonempty list
• Cases 1 and 2 requirement: Change value of the
pointer first
• Cases 3 and 4: After inserting an item, count
incremented by one

Data Structures Using C++ 2E 73

 Doubly Linked Lists (cont’d.)

• Insert a node (cont’d.)

– Figures 5-28 and 5-29 illustrate case 4
– See code on page 317
• Definition of the function insert

Data Structures Using C++ 2E 74

 Insert a node

Data Structures Using C++ 2E //end of while 75

 Insert a node

Data Structures Using C++ 2E 76

 Doubly Linked Lists (cont’d.)
• Delete a node
– Four cases
• Case 1: The list is empty
• Case 2: The item to be deleted is in the first node of the
list, which would require us to change the value of the
pointer first
• Case 3: The item to be deleted is somewhere in the list
• Case 4: The item to be deleted is not in the list
– See code on page 319
• Definition of function deleteNode

Data Structures Using C++ 2E 77

 Delete a node

Data Structures Using C++ 2E 78

 Delete a node

Data Structures Using C++ 2E 79

 Linked Lists with Header and Trailer
Nodes
• Simplify insertion and deletion
– Never insert item before the first or after the last item
– Never delete the first node
• Set header node at beginning of the list
– Containing a value smaller than the smallest value in
the data set
• Set trailer node at end of the list
– Containing value larger than the largest value in the
data set

Data Structures Using C++ 2E 80

 Linked Lists with Header and Trailer
Nodes (cont’d.)
• Header and trailer nodes
– Serve to simplify insertion and deletion algorithms
– Not part of the actual list
• Actual list located between these two nodes

Data Structures Using C++ 2E 81

 Circular Linked Lists

• Last node points to the first node

• Basic operations
– Initialize list (to an empty state), determine if list is
empty, destroy list, print list, find the list length, search
for a given item, insert item, delete item, copy the list

FIGURE 5-34 Circular linked lists

Data Structures Using C++ 2E 82
 Summary
• Linked list topics
– Traversal, searching, inserting, deleting
• Building a linked list
– Forward, backward
• Linked list as an ADT
• Ordered linked lists
• Doubly linked lists
• Linked lists with header and trailer nodes
• Circular linked lists

Data Structures Using C++ 2E 83