Linked List

1

List vs Arrays
Two built-in data structures that can be used to organize data, or to create other data structures:

• Lists • Arrays

Lists
A list is an ordered set of data. It is often used to store objects that are to be processed sequentially.

Arrays
An array is an indexed set of variables, such as dancer[1], dancer[2], dancer[3],… It is like a set of boxes that hold things. A list is a set of items. An array is a set of variables that each store an item.

Arrays and Lists
You can see the difference between arrays and lists when you delete items.

Arrays and Lists
In a list, the missing spot is filled in when something is deleted.

Arrays and Lists
In an array, an empty variable is left behind when something is deleted.

What’s wrong with Array and Why lists? • Disadvantages of arrays as storage data structures:
– slow searching in unordered array – slow insertion in ordered array – Fixed size

• Linked lists solve some of these problems • Linked lists are general purpose storage data structures and are versatile.

Linked Lists

A
Head

B

C



• A linked list is a series of connected nodes • Each node contains at least
– A piece of data (any type) – Pointer to the next node in the list

• Head: pointer to the first node • The last node points to NULL

node

A data pointer

The composition of a Linked List

• A linked list is called "linked" because each node in the series has a pointer that points to the next node in the list.

10

Linked Lists

• Each data item is embedded in a link. • Each Link object contains a reference to the next link in the list of items. • In an array items have a particular position, identified by its index. • In a list the only way to access an item is to traverse the list

Declarations to create a node

• First you must declare a data structure that will be used for the nodes. For example, the following struct could be used to create a list where each node holds a data: struct Node { int data; Node *next; };
12

data

Declarations
• The next step is to declare a pointer to serve as the list head, as shown below.
Node *head;

• Once you have declared a node data structure and have created a NULL head pointer, you have an empty linked list. • The next step is to implement operations with the list.
13

Operations in a simple linked list:
• Add or Append a node in the list void appendNode(value); • Insert a node in the list void insertNode(value); • Delete a node from the list void deleteNode(value); • Iterate through the list to display items.

void isplayList(value);

Adding or Appending a Node to the List

• To append a node to a linked list means to add the node to the end of the list. • The pseudocode is shown below. The C++ code follows. Create a new node. Store data in the new node. If there are no nodes in the list Make the new node the first node. Else Traverse the List to Find the last node. Add the new node to the end of the list. End If.
15

Void appendNode(int value)
{
Node *newNode, *curr; // Allocate a new node & store data newNode = new Node; newNode->data = value; newNode->next = NULL; // If there are no nodes in the list // make newNode the first node if (!head) head = newNode; else // Otherwise, insert newNode at end { // Initialize curr to head of list curr = head; // Find the last node in the list while (curr->next) curr = curr->next; // Insert newNode as the last node curr->next = newNode; } }
16

appendNode(int value) appendNode(2.5)

head = new Node;

Head

newNode = new Node; newNode->data = value; newNode->next = NULL;

17

Making first node as head
The next statement to execute is the following if statement. if (!head) head = newNode;

There are no more statements to execute

18

Append another node with the value 7.9. appendNode(7.9)
Once again, the first three statements in the function create a new node, store the argument in the node's data member, and assign its next pointer to NULL. newNode = new Node; newNode->data = value; newNode->next = NULL;

19

Since head no longer points to NULL, the else part of the if statement executes: else // Otherwise, insert newNode at end { // Initialize nodePtr to head of list curr = head; // Find the last node in the list while (curr->next) curr = curr->next; // Insert newNode as the last node curr->next = newNode; }

curr

curr

Append another node with the value 12.6. appendNode(12.6)

The third time appendNode is called, 12.6 is passed as the argument. Once again, the first three statements create a node with the argument stored in the value member. newNode = new Node; newNode->data = value; newNode->next = NULL;

21

Since head no longer points to NULL, the else part of the if statement executes: else // Otherwise, insert newNode at end { // Initialize nodePtr to head of list curr = head; // Find the last node in the list while (curr->next) curr = curr->next; // Insert newNode as the last node curr->next = newNode; }

curr curr

The while loop's conditional test will fail after the first iteration because curr->next now points to NULL. The last statement, curr->next = newNode; causes curr->next to point to the new node. This inserts newNode at the end of the list

curr

The figure above depicts the final state of the linked list.
23

Preliminaries

Figure 4.1 a) A linked list of integers; b) insertion; c) deletion
© 2005 Pearson Addison-Wesley. All rights reserved 4-24

Traversing or Displaying the List

• The displayList member function traverses the list, displaying the value member of each node. The following pseudocode represents the algorithm. The C++ code for the member function follows on the next slide.
Assign List head to node curr While curr is not NULL Display the value member of the curr. Assign curr to its own next member. End While.

25

displayList(void)
Void displayList(void) { Node *curr; curr = head; while (curr!=NULL) { cout value next; }

}

26

Inserting a Node

• Using the listNode structure again, the pseudocode on the next slide shows an algorithm for finding a new node’s proper position in the list and inserting there. • The algorithm assumes the nodes in the list are already in order.

27

Create a new node. Store data in the new node. If there are no nodes in the list Make the new node the first node. Else Find the first node whose value is greater than or equal the new value, or the end of the list (whichever is first). Insert the new node before the found node, or at the end of the list if no node was found. End If.

28

The code for the traversal algorithm is shown below. (As before, num holds the value being inserted into the list.)
// Initialize curr to head of list curr = head;
// Skip all nodes whose value member is less // than num. while (curr != NULL && curr->data < value) { previousNode = curr; curr = curr->next; }

The entire insertNode function begins on the next slide.

29

Inserting a Node into a Specified Position of a Linked List
• To insert a node between two nodes newPtr->next = cur; prev->next = newPtr;

Figure 4.12 Inserting a new node into a linked list

© 2005 Pearson Addison-Wesley. All rights reserved

4-30

Inserting a Node into a Specified Position of a Linked List
• To insert a node at the beginning of a linked list newPtr->next = head; head = newPtr;

Figure 4.13

Inserting at the beginning of a linked list

© 2005 Pearson Addison-Wesley. All rights reserved

4-31

Inserting a Node into a Specified Position of a Linked List
• Inserting at the end of a linked list is not a special case if cur is NULL newPtr->next = cur; prev->next = newPtr;

Inserting at the end of a linked list

Void insertNode(float vlaue)
{ Node *newNode, *curr, *previous; // Allocate a new node & store Num newNode = new Node; newNode->data = value; // If there are no nodes in the list // make newNode the first node if (head==NULL) { head = newNode; newNode->next = NULL; } else // Otherwise, insert newNode. { // Initialize nodePtr to head of list curr = head; // Skip all nodes whose value member is less than value. while (curr != NULL && curr->data < value) { previousNode = curr; curr = curr->next; }

Continued from previous slide.

// If the new mode is to be the 1st in the list, // insert it before all other nodes. if (previous == NULL) { head = newNode; newNode-> = curr;

} else { previous->next = newNode; newNode->next = curr; } } }

InsertNode with the value 10.5 curr a new node is created and the function argument is copied to its data member. Since the list already has nodes stored in it, the else part of the if statement will execute. It begins by assigning nodePtr to head.

Since curr is not NULL and curr->data is less than value, the while loop will iterate. During the iteration, previous will be made to point to the node that curr is pointing to. curr will then be advanced to point to the next node. curr while (curr != NULL && curr->data < value) { previousNode = curr; curr = curr->next; }

Once again, the loop performs its test. Since curr is not NULL and curr->data is less than value, the loop will iterate a second time. During the second iteration, both previousNode and curr are advanced by one node in the list. curr while (curr != NULL && curr->data < value) { previousNode = curr; curr = curr->next; 37 }

This time, the loop's test will fail because curr is not less than value. The statements after the loop will execute, which cause previousNode->next to point to newNode, and newNode->next to point to curr. curr If you follow the links, from the head pointer to the NULL, you will see that the nodes are stored in the order of their value members.
38

Deleting a Node

• Deleting a node from a linked list requires two steps:
– Remove the node from the list without breaking the links created by the next pointers – Deleting the node from memory

• The deleteNode function begins on the next slide.

39

Void deleteNode(float value) { ListNode *curr, *previousNode; // If the list is empty, do nothing. if (!head) return; // Determine if the first node is the one. if (head->data == value) { curr = head->next; delete head; head = curr; }

Continued on next slide…
40

Continued from previous slide. else { // Initialize nodePtr to head of list curr = head;

// Skip all nodes whose value member is // not equal to num. while (curr != NULL && curr->data != value) { previousNode = curr; curr = curr->next; }
// Link the previous node to the node after // nodePtr, then delete nodePtr. previousNode->next = curr->next; delete curr; } }
41

Deleting a Specified Node from a Linked List

Deleting a node from a linked list

Deleting the first node
4-42

Look at the else part of the second if statement. This is where the function will perform its action since the list is not empty, and the first node does not contain the value 7.9. Just like insertNode, this function uses curr and previousNode to traverse the list. The while loop terminates when the value 7.9 is located. At this point, the list and the other pointers will be in the state depicted in the figure below.

43

next, the following statement executes.

previousNode->next = curr->next;
The statement above causes the links in the list to bypass the node that curr points to. Although the node still exists in memory, this removes it from the list.

The last statement uses the delete operator to complete the total deletion of the node. 44

Variations of Linked Lists
• Circular linked lists
– The last node points to the first node of the list
A Head B C

– How do we know when we have finished traversing the list? (Tip: check if the pointer of the current node is equal to the head.)

Variations of Linked Lists
• Doubly linked lists
– Each node points to not only successor but the predecessor – There are two NULL: at the first and last nodes in the list – Advantage: given a node, it is easy to visit its predecessor. Convenient to traverse lists backwards
 A B C 

Head

Array versus Linked Lists

• Linked lists are more complex to code and manage than arrays, but they have some distinct advantages.
– Dynamic: a linked list can easily grow and shrink in size.
• We don’t need to know how many nodes will be in the list. They are created in memory as needed. • In contrast, the size of a C++ array is fixed at compilation time.

– Easy and fast insertions and deletions
• To insert or delete an element in an array, we need to copy to temporary variables to make room for new elements or close the gap caused by deleted elements. • With a linked list, no need to move other nodes. Only need to reset some pointers.

Comparing Array-Based and Pointer-Based Implementations
• Size
– Increasing the size of a resizable array can waste storage and time

• Storage requirements
– Array-based implementations require less memory than a pointer-based ones

4-48

Comparing Array-Based and Pointer-Based Implementations
• Access time
– Array-based: constant access time – Pointer-based: the time to access the ith node depends on i

• Insertion and deletions
– Array-based: require shifting of data – Pointer-based: require a list traversal

4-49

Doubly Linked Lists
• To delete the node to which cur points
(cur->precede)->next = cur->next; (cur->next)->precede = cur->precede;

• To insert a new node pointed to by newPtr before the node pointed to by cur newPtr->next = cur; newPtr->precede = cur->precede; cur->precede = newPtr; newPtr->precede->next = newPtr;

4-50

Application: Maintaining an Inventory
• Operations on the inventory
– List the inventory in alphabetical order by title (L command) – Find the inventory item associated with title (I, M, D, O, and S commands) – Replace the inventory item associated with a title (M, D, R, and S commands) – Insert new inventory items (A and D commands)
© 2005 Pearson Addison-Wesley. All rights reserved 4-51