Chapter 3

Linked Lists
 Our First Data Structure
◦ Linked Lists
 Singly
 Doubly
 Circular
 This week we will look at linked lists.
◦ Why to use linked lists?
◦ How to use linked lists?
◦ Different Types of linked list.
 But first, lets review arrays.
◦ A very useful structure provided by programming
languages
◦ However, arrays have at least 2 limitations;
 The size has to be known at compilation.
 The data in the array are separated in the computers
memory by the same distance.
◦ These limitations make ‘inserting’ an item inside
the array difficult.
 Linked Lists can be used to get around the
limitations of arrays by linking data
independently from where it is stored in the
computers memory.
 To create a linked list, each piece of data in

the set of data, simply has to also store the

address of the next piece of data in the set.
P

Data Data Data Data Data

0
 A linked structure is a collection of nodes
storing data and links to other nodes.
 Nodes can be located anywhere in memory,

and passing from one node of the linked

structure to another is accomplished by
storing the addresses of other nodes in the
linked structure.
 a data structure that makes it easy to
rearrange data without having to move data
in memory.

 Ex1:
 picture a classroom of students who are
seated in no particular order. A unique
number identifies each seat (see next
figure). We’ve also included the relative
height of each student, which we’ll use in
the next exercise.
Let’s say that a teacher needs to place students
names in alphabetical order so she can easily find a
name on the list.
 Solutions:
 Change their seats (chaotic if many)
 leave students seated and make a list of seat

numbers that corresponds to the alphabetical

order of students (3,1,2)
Ex2: Suppose you want to rearrange students
in size order.(1,3,2)
• play a critical role in applications that help
companies and governments manage data
dynamically.
• A single link list enables a program to move
through the list in one direction, which is
usually from the front of the list moving to
the end of the list. A doubly linked list
enables the program to move through the list
in both directions.
 Programmers choose linked lists over an
array because linked lists can grow or shrink
in size during runtime. Another entry can be
placed at the end of the last entry on the
linked list simply by assigning reference to
the new entry in the last entry on the linked
list.
 the last entry can be removed from the linked
list by simply removing reference to it in the
next element of the second-to-last entry on
the linked list. This is more efficient than
using an array and resizing at runtime.
 change the size of the array, the operating
system tries to increase the array by using
memory alongside the array. If this location is
unavailable, then the operating system finds
another location large enough to hold
elements of the array and new array
elements. Elements of the array are then
copied to the new location.
 change the size of a linked list, the operating
system changes references to the previous
item and the next item on the list, which is
fewer steps than changing the size of an
array.
 Node - each entry in a linked list
• typedef struct Node
{  \\ constructor initializes elements of the node when an instance
of the \\node is created
 struct Node(int data) \\ structure name creates
instance
   {    
this->data = data;   
    previous = NULL;      \\pointers to the previous
  next = NULL;   \\and next node in the link
list
}
  int data;  
struct Node* previous;  
struct Node* next;
} NODE;
Example: Create a linked list of structures

• Last member of the structure is a pointer for

storing the address of another structure of the
same type
Example: Using the linked list of structures
Steps
1. Allocate memory for the new node.
2. Point the new node to its successor.
3. Point the new node’s predecessor to the new
node.
Figure 3-10: Adding node to an empty list.
Figure 3-11: Add node at the beginning.
Figure 3-12: Insert in a middle.
Figure 3-13: Add node at end.
algorithm insertNode (
ref list <metadata>, 5 if (pPre nulll)
val pPre <node pointer> Adding before first node
val dataIn <dataType>) or to
Inserts data into a new node in the linked list
empty list.
Pre list is metadata structure to a
valid list pPre is pointer to data’s 1 pNew->link = list.head
logical predecessor dataIn 2 list.head = pNew
contains 6 else
data to be inserted
Adding in middle or at
Post data have been inserted in end.
sequence
Return true if successful, false if 1 pNew->link = pPre->link
memory overflow 2 pPre->link = pNew
1 allocate (pNew) 7 end if
2 if (memory overflow) 8 list.count = list.count + 1
1 return false 9 return true
3 end if
end insertNode
4 pNew->data = dataIn
nodeType *newNode;
newNode = new nodeType;
newNode->data = 123;
newNode->link = current->link;
current->link = newNode;
 
while(current)
  {
        if((current->data < data) && (current->next-
>data > data))
    {
            temp = current->next;
            current->next = newnode;
            newnode->next = temp;
            break;
    }
        current = current->next;
  }
 The example on the previous page was an
example of a singly linked list.
◦ A pointer (P) to the first element in the list
◦ Each element stores some data, and a pointer to
the next element in the list
◦ The final element points towards NULL (0), to
indicate it is the final element.
 The data stored in a linked list can be
anything from a simple integer to a user
defined class.
node in a single linked list references the next node
and not the previous node, although nothing stops
you from creating a backward reference by using
only the previous node reference
This enables the programmer to traverse the linked
list in both directions by referencing the previous
and next nodes.
The appendNode() member function places a new
node at the end of the linked list.
void appendNode(int data)
{ 
NODE* n = new NODE(data);  
if(back == NULL)
 {   
back = n;    
front = n;
 }
 else
 {
back->next = n;
n->previous = back;  
back = n;  
}
}
 Step 1: assigns the memory address of the new
node to the next member of the back node, shown
in the second block of memory

 Step2: assigns the memory address of the back

node to the previous member of the new node.
This links both nodes.

 Step 3:replaces the memory address of the back

node on the linked list with the memory address of
the new node. This places the new node at the
beginning of the linked list.
 displayNodes() member function displays each
node of the linked list, beginning with the node at
the front of the list and ending with the node at the
back of the list.
void displayNodes()
{ 
cout << "Nodes:";   NODE* temp = front;   
while(temp != NULL)
{
     cout << " " << temp->data;
     temp = temp->next;
}
}
• displayNodesReverse() member function displays
the contents of a linked list in reverse order, beginning
with the node at the back of the linked list and
continuing until the first node is displayed.
• void displayNodesReverse()
{   
cout << "Nodes in reverse order:";  
 NODE* temp = back;   
while(temp != NULL)  
 {       cout << " " <<  temp->data;      
temp = temp->previous;
}
}
Figure 3-14: Deleting the first node in the list.
Figure 3-15: Deleting nodes in between other two nodes.

Question: How about deleting the last node?

algorithm deleteNode(
ref list <metadata>, 1 dataOut = pLoc->data
val pPre <node pointer>
2 if (pPre null)
val pLoc <node pointer>
Deleting first node
ref dataOut <dataType>)
Deletes data from a linked list and 1 list.head = pLoc->link
returns it calling module 3 else
Pre list is a metadata structure to a Deleting other nodes
valid list
1 pPre->link = pLoc.link
pPre is a pointer to predecessor
node 4 end if
pLoc is a pointer to node to be
deleted 5 list.count = list.count - 1
dataOut is variable to receive deleted 6 recycle (pLoc)
data
7 return
Post data have been deleted and
returned to caller end deleteNode
• destroyList() member function removes nodes from the
linked list without removing the linked list itself.
void destroyList()
{
  NODE* temp = back;  
 while(temp != NULL)
  {     
 NODE* temp2 = temp;      
temp = temp->previous;
delete temp2;   
} 
 back = NULL;   front = NULL;
}
removing the linked list itself
while(current!=NULL)
  {
        if(current->data!=data)
    {
            prev=current;
            current = current->next;
    }
        else
    {
            prev->next = current->next;
            delete current;
            break;
    }
  }
 Another type of Linked List is a circular linked
list
◦ Here the final node in the list points back to the
first node.
◦ This can be useful for tracking things continually in
sequence
Figure 3-21 A circularly linked list

The last node’s link points to the first node

 The delete from tail function highlighted a
difficulty inherent in singly linked lists.
◦ In order to find the last element in a list, we have to
scan through the entire list till we find the element
pointing to NULL, we then have to delete this
element, while tracking the previous element and
pointing that to NULL.
 If we are dealing with a long list, or frequent
tail_delete function calls, it may be useful to
have a Doubly Linked List.
Head Tail

Data Data Data

0
0
Figure 3-22 A doubly linked list`

A linked list structure in which each node has pointer to both its successor
and its predecessor.

Three pieces of metadata of the Each node contains two pointers:

head structure: 1. Backward pointer – points to its
1. Count predecessor
2. Position pointer for traversals 2. Forward pointer – points to its
3. Rear pointer (optional) successor
Figure 3-23 Doubly linked list insert
Figure 3-24 Doubly linked list delete
 Searching a singly linked list involves starting
at the head and following the pointers
through the list until either the node is found
or the tail is reached.
 A temporary pointer is used, tmp, where at

each step it is pointed to the following node,

tmp->next.
 the process used to find the location of a
target among a list of objects.
 Sequential search
 Binary search
 normally used when a list is not sorted
 it starts at the beginning of the list and

searches until it finds the data or hits the

end of the list
 in a sorted list, the search terminates when

the target is less than the current element.

It needs to tell the calling algorithm . . .
1. Find the data it was looking for;
2. What index are the target data found.
It requires four parameters.
◦ List we are searching.
◦ Index to the last element in the list (or size).
◦ The target.
◦ The address where the found element’s index
location is to be stored.
Figure 2-1: Locating data in unordered list
Figure 2-2: Search concept
Figure 2-3: Unsuccessful search in unordered list.
The sequential search algorithm.

1. looker = 0
2. loop (looker < last AND target not equal
list[looker])
1. looker = looker + 1
3. end loop
4. location = looker
5. if (target equal list[looker])
1. found = true
6. else
1. found = false
7. end if
8. return found
 Generally, to find a value in unsorted array, we should look through
elements of an array one by one, until searched value is found. In
case of searched value is absent from array, we go through all
elements. In average, complexity of such an algorithm is proportional to
the length of the array.
 Situation changes significantly, when array is sorted. If we know it,
random access capability can be utilized very efficiently to find
searched value quick. Cost of searching algorithm reduces to binary
logarithm of the array length. For reference, log 2(1 000 000) ≈ 20. It
means, that in worst case, algorithm makes 20 steps to find a value in
sorted array of a million elements or to say, that it doesn't present it the
array.
Algorithm
Algorithm is quite simple. It can be done either recursively or iteratively:
1. get the middle element;
2. if the middle element equals to the searched value, the algorithm
stops;
3. otherwise, two cases are possible:
◦ searched value is less, than the middle element. In this case, go
to the step 1 for the part of the array, before middle element.
◦ searched value is greater, than the middle element. In this case,
go to the step 1 for the part of the array, after middle element.
Figure 2-4: Binary search example.
Figure 2-5
1. First = 0
2. Last = end
3. Loop (first <= last)
1. Mid = (first + last)/2
2. If (target > list[mid])
Look in the upper half
 First = mid + 1
3. Else if (target < list[mid])
Look in the lower half
1. Last = mid – 1
4. Else
5. Found equal : force exit
1. First = last + 1
6. End if
4. End loop
5. Locn = mid
6. If (target equal list[mid])
1. Found = true
7. Else
1. Found = false
8. End if
9. Return found
1. First = 0, Last =
list.size() - 1
2. while (first <= last)
1. Mid = (first + last)/2
2. If (list[mid] < target])
Look in the upper half
 First = mid + 1
3. Else if (target < list[mid])
Look in the lower half
1. Last = mid – 1
4. Else
1. Return mid
5. End if
3. End loop
4. Return -1
/*
* searches for a value in sorted array
*   arr is an array to search in
*   value is searched value
*   left is an index of left boundary
*   right is an index of right boundary
* returns position of searched value, if it presents in the array
* or -1, if it is absent
*/
int binarySearch(int arr[ ], int value, int left, int right) {
      while (left <= right) {
            int middle = (left + right) / 2;
            if (arr[middle] == value)
                  return middle;
            else if (arr[middle] > value)
                  right = middle - 1;
            else
                  left = middle + 1;
      }
      return -1;