Chapter Three

Linked Lists

Course Title:- Data structure and

Algorithms
Instructor:- Feyisa K.
Email:- [email protected]
 Outlines
Review on Pointers, Dynamic Memory allocation
and De-allocation
Singly Linked Lists
Doubly Linked Lists
Circular Linked Lists

2
 Review on Pointers, Dynamic Memory allocation and De-allocation
 Although C++ supports all the functions (i.e., malloc,
calloc, realloc and free) used in C, it also defines two
unary operators new and delete that performs the task of
allocating and freeing the memory in a better and easier
way.
 An object (or variable) can be created by using new, and
destroyed by using delete, as and when required.
 A data object created inside a block with new, will remain
in existence until it is explicitly destroyed by using delete.
Thus, the lifetime of an object is directly under our control
and is unrelated to the block structure of the program.

3
 Cont…
 The new operator can be used to create objects of any type. It takes the following
general form:
 Pointer_Variable = new data_type;
 Here, Pointer_Variable is a pointer of type data_type. The new operator allocates
sufficient memory to hold a data object of type data_type and returns the address of
the object. The data_type may be any valid data type. The Pointer_Variable holds the
address of the memory space allocated.
 For example:
 int *Var1 = new int;
 float *Var2 = new float;
 Where Var1 is a pointer of type int and Var2 is a pointer of type float.
 When a data object is no longer needed, it is destroyed to release the memory space
for reuse. The general form of its use is:
 delete Pointer_Variable;
 The Pointer_Variable is the pointer that points to a data object created with new.
 delete Var1;
 delete Var2

4
 Structures
 Structures are aggregate data types built using elements of primitive data types.
Structure are defined using the struct keyword:
 E.g. struct Time{

int hour;
int minute;
int second;
};
 The struct keyword creates a new user defined data type that is used to declare
variables of an aggregate data type. Structure variables are declared like variables
of other types.
 Syntax: struct <structure tag> <variable name>;
 E.g. struct Time timeObject,
struct Time *timeptr;

5
 Cont…
Accessing Members of Structure Variables
 The Dot operator (.): to access data members of structure variables.

 The Arrow operator (->): to access data members of pointer

variables pointing to the structure.

 E.g. Print member hour of timeObject and timeptr.

cout<< timeObject.hour; or

cout<<timeptr->hour;
 TIP: timeptr->hour is the same as (*timeptr).hour.

 The parentheses is required since (*) has lower precedence than (.).

6
 Cont…
Self-Referential Structures
 Structures can hold pointers to instances of themselves.
struct car{
char name[10];
int speed;
struct list *next;
};
 However, structures cannot contain instances of themselves.

7
 Linked Lists
 If the memory is allocated for the variable during the compilation (i.e.
before execution) of a program, then it is fixed and cannot be changed.
 For example, an array A[100] is declared with 100 elements, then the
allocated memory is fixed and cannot be decreased and increased the
SIZE of the array if required.
 So we have to adopt an alternative strategy to allocate memory only
when it is required. There is a special data structure called linked list
that provides a more flexible storage system and it does not require the
use of arrays.
 A linked list is a linear collection of specially designed data elements,
called nodes, linked to one another by means of pointers.
 Each node is divided into two parts: the first part contains the
information of the elements, and the second part contains the address
of the next node in the linked list. Address part of the node is also
called linked or next field.
8
 Cont…

Figure 3. Linked List representation in memory

9
 Cont…
 Each node is pictured with two parts.
 The left part of each node contains the data items and the
right part represents the address of the next node; there is an
arrow drawn from it to the next node.
 The next pointer of the last node contains a special value,
called the NULL pointer, which does not point to any
address of the node. That is NULL pointer indicates the end
of the linked list. START pointer will hold the address of the
1st node in the list START =NULL if there is no list (i.e.;
NULL list or empty list).

10
 Advantages and Disadvantages of Linked Lists
Some of the advantages of Linked list are:
1. Linked list are dynamic data structure. That is, they can grow or shrink during the
execution of a program.
2. Efficient memory utilization: In linked list (or dynamic) representation, memory is
not pre-allocated. Memory is allocated whenever it is required. And it is deallocated
(or removed) when it is not needed.
3. Insertion and deletion are easier and efficient. Linked list provides flexibility in
inserting a data item at a specified position and deletion of a data item from the given
position.
4. Many complex applications can be easily carried out with linked list.
Linked list has following the disadvantages
5. More memory: to store an integer number, a node with integer data and address field
is allocated. That is more memory space is needed.
6. Access to an arbitrary data item is little bit cumbersome (complex) and also time
consuming.
11
 Operation on linked list
The primitive operations performed on the linked list are as follows
 Creation
 Insertion
 Deletion
 Traversing
 Searching
 Concatenation
1. Creation operation is used to create a linked list. Once a linked list is
created with one node, insertion operation can be used to add more
elements in a node.
2. Insertion operation is used to insert a new node at any specified
location in the linked list. A new node may be inserted.
(a) At the beginning of the linked list
(b) At the end of the linked list
(c) At any specified position in between in a linked list

12
 Cont..
3.Deletion operation is used to delete an item (or node) from the
linked list. A node may be deleted from the
(a) Beginning of a linked list
(b) End of a linked list
(c) Specified location of the linked list
4.Traversing is the process of going through all the nodes from one
end to another end of a linked list. In a singly linked list we can
visit from left to right, forward traversing only. But in doubly linked
list forward and backward traversing is possible.
5.Concatenation is the process of appending the second list to the
end of the first list.
 Consider a list A having n nodes and B with m nodes. Then the
operation concatenation will place the 1st node of B in the (n+1)th
node in A. After concatenation A will contain (n+m) nodes
13
 Types of Linked Lists
 Basically we can divide the linked list into the following three
types in the order in which they (or node) are arranged.
 Singly linked list
 Doubly linked list
 Circular linked list

14
 Creating Singly Linked Lists in C++
 A linked list is a data structure that is built from
structures and pointers.
 It forms a chain of "nodes" with pointers representing
the links of the chain and holding the entire thing
together.
 A linked list can be represented by a diagram like this
one:

15
 cont…
This linked list has four nodes in it, each with a link to the
next node in the series.
The last node has a link to the special value NULL, which
any pointer (whatever its type) can point to, to show that it
is the last link in the chain.
There is also another special pointer, called Start (also
called head), which points to the first link in the chain so
that we can keep track of it.
Defining the Data Structure for A Linked List
The key part of a linked list is a structure, which holds the
data for each node (the name, address, age or whatever for
the items in the list), and, most importantly, a pointer to the
next node.
Here we have given the structure of a typical node:
16
 Cont…
struct Person
{
char name[20]; // name of up to 20 letters
int age
float height; // in metres
Person *next; //Pointer to next node
};
struct Person *start_ptr = NULL;

 The important part of the structure is the line before the closing curly brackets.
 This gives a pointer to the next node in the list. This is the only case in C++ where
you are allowed to refer to a data type (in this case Person) before you have even
finished defining it!
 We have also declared a pointer called start_ptr that will permanently point to the
start of the list. To start with, there are no nodes in the list, which is why start_ptr is
set to NULL.
17
 Adding a Node to the List
 The first problem that we face is how to add a node to the list.
 For simplicity's sake, we will assume that it has to be added to the end of
the list, although it could be added anywhere in the list (a problem we will
deal with later on).
 Firstly, we declare the space for a pointer item and assign a temporary
pointer to it. This is done using the new statement as follows:
temp = new Person();

 We can refer to the new node as *temp, i.e. "the node that temp points to".
 When the fields of this structure are referred to, brackets can be put round the
*temp part, as otherwise the compiler will think we are trying to refer to the
fields of the pointer.
 Alternatively, we can use the arrow pointer notation.
18
 cont…
 Having declared the node, we ask the user to fill in the details of the
person, i.e. the name, age, address or whatever:
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->next = NULL;
 The last line sets the pointer from this node to the next to NULL, indicating
that this node, when it is inserted in the list, will be the last node.
 Having set up the information, we have to decide what to do with the
pointers.of course, if the list is empty to start with, there's no problem - just
set the Start pointer to point to this node (i.e. set it to the same value as
temp):
if (start_ptr == NULL)
start_ptr = temp;

19
 cont…
I. Adding At the End
 It is harder if there are already nodes in the list. In this case, the secret is to declare a
second pointer, temp2, to step through the list until it finds the last node.

temp2 = start_ptr;
//We know this is not NULL - list not empty!
while (temp2->next != NULL)
{
temp2 = temp2->next; // Move to next link in chain
}
20
 Cont…
 The loop will terminate when temp2 points to the last node in the chain,
and it knows when this happened because the next pointer in that node
will point to NULL. When it has found it, it sets the pointer from that
last node to point to the node we have just declared:
temp2->next = temp;

 The link temp2->next in this diagram is the link joining the last two
nodes.
21
 Cont…
 The full code for adding a node at the end of the list is shown below, in its
own little function:
void add_node_at_end ()
{
Person *temp, *temp2; // Temporary pointers
// Reserve space for new node and fill it with data
temp = new Person;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->next = NULL;

22
 Cont…
// Set up link to this node
if (start_ptr == NULL)
start_ptr = temp;
else {
temp2 = start_ptr;
//We know this is not NULL - list not empty!
while (temp2->next != NULL)
{
//Move to next link in chain
temp2 = temp2->next;
}
temp2->next = temp;
}
}
23
 Cont…
II. Adding Node at the Beginning
 Adding a node to the beginning of linked list is much easier
than adding to the end. The start_ptr should be made to point
to the new node:
temp->next = start_ptr;
start_ptr = temp; //the new node will be the head of the list
 Remember that start_ptr (head) should point to the first node in the
linked list.
 Hence, when you add node at the beginning, you have to reposition
head to the new node.
 What do you think would happen if start_ptr does not point to the
first node in the list?
24
 Cont…
III. Adding Node in the Middle
 Adding a node to the middle of linked list is a little bit trickier than adding
at beginning or end. We have to find the exact node which is going to point
to our new node.
 Suppose we want to add the new node after a list with a name “Sue”

 First we have to navigate through the list and find which node has the
name “Sue”. After it is found, we have to make the new node point to the
node next to node with value “Sue”. Then the node with value “Sue” can
point to the new node. This can be done with the following code:
25
 Cont…
void add_in_middle()
{
Person *trav;
trav = head;
while(trav != NULL)
{
if(strcmp(trav->name, “Sue”)==0)
break;
trav=trav->next;
}
if(trav != NULL) //searched node found
{
temp->next=trav->next;
trav->next = temp;
}
}
26
 Cont…
Caution
 There is a possibility that you may lose the right half of the list if
not careful while adding to the middle. This happens if you don’t
make temp to point to node next to the node with value “Sue”.

27
 Displaying the List of Nodes
 Having added one or more nodes, we need to display the list of
nodes on the screen. This is comparatively easy to do. Here is the
method:
1. Set a temporary pointer to point to the same thing as the start pointer.
2. If the pointer points to NULL, display the message "End of list" and
stop.
3. Otherwise, display the details of the node pointed to by the
temporary pointer.
4. Make the temporary pointer point to the same thing as the next
pointer of the node it is currently pointing to.
5. Jump back to step 2.
 The temporary pointer moves along the list, displaying the
details of the nodes it comes across.
28
At each stage, it can get hold of the next node in the list by
 Cont…
 Here is the C++ code that does the job:
void display()
{
temp = start_ptr;
do
{
if (temp == NULL)
cout << "End of list" << endl;
else
{
//display details for what temp points to
cout << "Name : " << temp->name << endl;

29
 Cont…
cout << "Age : " << temp->age << endl;
cout << "Height : " << temp->height << endl;
cout << endl; // blank line
// Move to next node (if present)
temp = temp->next;
}
} while (temp != NULL);
}
 Check through this code, matching it to the method listed above. It
helps if you draw a diagram on paper of a linked list and work
through the code using the diagram.

30
 Navigating Through the List
 One thing you may need to do is to navigate through the
list, with a pointer that moves backwards and forwards
through the list, like an index pointer in an array.
 This is certainly necessary when you want to insert or
delete a node from somewhere inside the list, as you will
need to specify the position.
 We will call the mobile pointer current. First of all, it is
declared, and set to the same value as the start_ptr
pointer:
Person *current;
current = start_ptr;
31
 Cont…
 Notice that you don't need to set current equal to the
address of the start pointer, as they are both pointers. The
statement above makes them both point to the same
thing:

 It's easy to get the current pointer to point to the next

node in the list i.e. move from left to right along the list.
 If you want to move current along one node, use the next
field of the node that it is pointing to at the moment:
32 current = current->next;
 Cont…
 In fact, we had better check that it isn't pointing to the
last item in the list. If it is, then there is no next node to
move to:
if (current->next == NULL)
cout << "You are at the end of the list." << endl;
else
current = current->next;
 Moving the current pointer back one step is a little harder. This is
because we have no way of moving back a step automatically from
the current node.
 The only way to find the node before the current one is to start at

33 the beginning, work our way through and stop when we find the
node before the one we are considering at the moment.
 Cont…
 We can tell when this happens, as the next pointer from
that node will point to exactly the same place in memory
as the current pointer (i.e. the current node).

 First of all, we had better check to see if the current node

is also first the one. If it is, then there is no "previous"
node to point to. If not, check through all the nodes in
turn until we detect that we are just behind the current
34
one
 Cont…
if (current == start_ptr)
cout << "You are at the start of the list" << endl;
else
{
Person *previous; // Declare the pointer
previous = start_ptr;

while (previous->next != current)

{
previous = previous->next;
}
current = previous;
}

35
 Cont…
 The else clause translates as follows: declare a temporary pointer
(for use in this else clause only). Set it equal to the start pointer.
 All the time that it is not pointing to the node before the current
node, move it along the line. Once the previous node has been
found, the current pointer is set to that node - i.e. it moves back
along the list.
 Now that you have the facility to move back and forth, you need to
do something with it. Firstly, let's see if we can alter/modify the
details for that particular node in the list:
cout << "Please enter the new name of the person: ";
cin >> current->name;
cout << "Please enter the new age of the person : ";
cin >> current->age;
cout << "Please enter the new height of the person : ";
36cin >> current->height;
 Cont…
 The next easiest thing to do is to delete a node from the list directly
after the current position. We have to use a temporary pointer to
point to the node to be deleted.
 Once this node has been "anchored", the pointers to the remaining
nodes can be readjusted before the node on death row is deleted.
Here is the sequence of actions:
1. Firstly, the temporary pointer is assigned to the node
after the current one. This is the node to be deleted:

37
 Cont…
2. Now the pointer from the current node is made to leap-frog the
next node and point to the one after that:

3. The last step is to delete the node pointed to by temp.

38
 Cont…
 Here is the code for deleting the node. It includes a test at the start
to test whether the current node is the last one in the list:
if (current->next == NULL)
cout << "There is no node after current" << endl;
else
{
Person *temp;
temp = current->next;
current->next = temp->next; // could be NULL
delete temp;
}

39
 Cont…

 We have assumed that the function add_node_at_end() is the

routine for adding the node to the end of the list that we created
near the top of this section. This routine is called if the current
pointer is the last one in the list so the new one would be added on
to the end.
 Similarly, the routine get_details(temp) is a routine that reads in
the details for the new node similar to the one defined just above.

40
 Deleting A Node From The List
 When it comes to deleting nodes, we have three choices: delete a
node from the start of the list, delete one from the end of the list, or
delete one from somewhere in the middle. For simplicity, we shall
just deal with deleting one from the start or from the end.
 When a node is deleted, the space that it took up should be
reclaimed. Otherwise the computer will eventually run out of
memory space. This is done with the delete instruction:
delete temp; // Release the memory pointed to by temp
 However, we can't just delete the nodes willy-nilly as it would
break the chain. We need to reassign the pointers and then delete
the node at the last moment. Here is how we go about deleting the
first node in the linked list:

temp = start_ptr; //make the temp pointer identical to the start

41pointer
 Cont…

 Now that the first node has been safely tagged (so that we can refer
to it even when the start pointer has been reassigned), we can move
the start pointer to the next node in the chain:
start_ptr = start_ptr->next; //second node in chain.

42
 Cont…
delete temp; //wipe out original start node

Here is the function that deletes a node from the start:

void delete_start_node()
{
Person *temp;
temp = start_ptr;
start_ptr = start_ptr->next;
delete temp;
}
43
 Cont…
 Deleting a node from the end of the list is harder, as the temporary
pointer must find where the end of the list is by hopping along
from the start.
 This is done using code that is almost identical to that used to
insert a node at the end of the list.
 It is necessary to maintain two temporary pointers, temp1 and
temp2.
 The pointer temp1 will point to the last node in the list and temp2
will point to the previous node.
 We have to keep track of both as it is necessary to delete the last
node and immediately afterwards, to set the next pointer of the
previous node to NULL (it is now the new last node).

44
 Cont…
1. Look at the start pointer. If it is NULL, then the list is empty, so print
out a "No nodes to delete" message.
2. Make temp1 point to whatever the start pointer is pointing to.
3. If the next pointer of what temp1 indicates is NULL, then we've
found the last node of the list, so jump to step 7.
4. Make another pointer, temp2, point to the current node in the list.
5. Make temp1 point to the next item in the list.
6. Go to step 3.
7. If you get this far, then the temporary pointer, temp1, should point to
the last item in the list and the other temporary pointer, temp2,
should point to the last-but-one item.
8. Delete the node pointed to by temp1.
9. Mark the next pointer of the node pointed to by temp2 as NULL - it
is the new last node.

45
 Cont…
 Let's try it with a rough drawing. This is always a good idea
when you are trying to understand an abstract data type.
 Suppose we want to delete the last node from this list:

 Firstly, the start pointer doesn't point to NULL, so we don't

have to display a "Empty list, wise guy!" message. Let's get
straight on with step2 - set the pointer temp1 to the same as
the start pointer:

46
 Cont…
 The next pointer from this node isn't NULL, so we haven't
found the end node. Instead, we set the pointer temp2 to the
same node as temp1

 and then move temp1 to the next node in the list:

47
 Cont…
 Going back to step 3, we see that temp1 still doesn't point to
the last node in the list, so we make temp2 point to what
temp1start_ptr
points to.
       
NULL

temp 2 temp1

 and temp1 is made to point to the next node along:

48
 Cont…
 Eventually, this goes on until temp1 really is pointing to the
last node in the list, with temp2 pointing to the penultimate
node:

 Now we have reached step 8. The next thing to do is to delete

the node pointed to by temp1

49
 Cont…
 and set the next pointer of what temp2 indicates to NULL

 We suppose you want some code for all that! All right then ....
void delete_end_node()
{
Person *temp1, *temp2;
if (start_ptr == NULL)
cout << "The list is empty!" << endl;
else
{
temp1 = start_ptr;
50
 Cont…
while (temp1->next != NULL)
{
temp2 = temp1;
temp1 = temp1->next;
}
delete temp1;
temp2->next = NULL;
}
}
 The code seems a lot shorter than the explanation!

51
 Cont…
 Now, the sharp-witted amongst you will have spotted a
problem. If the list only contains one node, the code above
will malfunction.
 This is because the function goes as far as the
temp1=start_ptr statement, but never gets as far as setting up
temp2.
 The code above has to be adapted so that if the first node is
also the last (has a NULL next pointer), then it is deleted and
the start_ptr pointer is assigned to NULL.
 In this case, there is no need for the pointer temp2:

52
 Cont…
void delete_end_node()
{
Person *temp1, *temp2;
if (start_ptr == NULL)
cout << "The list is empty!" << endl;
else {
temp1 = start_ptr;
if (temp1->next == NULL) // This part is new!
{
delete temp1;
start_ptr = NULL;
}

53
 Cont…
else {
while (temp1->next != NULL)
{
temp2 = temp1;
temp1 = temp1->next;
}
delete temp1;
temp2->next = NULL;
}
}
}

54
 Doubly Linked Lists
 That sounds even harder than a linked list! Well, if you've
mastered how to do singly linked lists, then it shouldn't
be much of a leap to doubly linked lists.
 A doubly linked list is one where there are links from
each node in both directions:

55
 Cont…
 You will notice that each node in the list has two
pointers, one to the next node and one to the previous one
- again, the ends of the list are defined by NULL pointers.
 Also there is no pointer to the start of the list. Instead,
there is simply a pointer to some position in the list that
can be moved left or right.
 The reason we needed a start pointer in the ordinary
linked list is because, having moved on from one node to
another, we can't easily move back, so without the start
pointer, we would lose track of all the nodes in the list
that we have already passed.
 With the doubly linked list, we can move the current
56 pointer backwards and forwards at will.
 Creating Doubly Linked Lists
 The nodes for a doubly linked list would be defined as
follows:
struct Person
{
char name[20];
Person *next; // Pointer to next node
Person *prev; // Pointer to previous node
};
Person *current;
current = new Person;
strcpy(current->name, "Fred");
current->next = NULL;
current->prev = NULL;

57
 Creating Doubly Linked Lists
 We have also included some code to declare the first
node and set its pointers to NULL. It gives the following
situation:

 We still need to consider the directions 'forward' and

'backward', so in this case, we will need to define
functions to add a node to the start of the list (left-most
position) and the end of the list (right-most position).

58
 Adding a Node to a Doubly Linked List
void add_node_at_start (string new_name)
{
//Declare a temporary pointer and move it to the start
Person *temp = current;
while (temp->prev != NULL)
temp = temp->prev;
//Declare a new node and link it in
Person *temp2;
temp2 = new Person;
strcpy(temp2->name, new_name); //store new name in the node
temp2->prev = NULL; // This is the new start of the list
temp2->next = temp; // Links to current list
temp->prev = temp2;
}

59
 Adding a Node to a Doubly Linked List
void add_node_at_end ()
{
//Declare a temporary pointer and move it to the end
Person *temp = current;
while (temp->next != NULL)
temp = temp->next;
//declare a new node and link it in
Person *temp2;
temp2 = new Person;
strcpy(temp2->name, new_name); //Store new name in the node
temp2->next = NULL; // This is the new start of the list
temp2->prev = temp; // Links to current list
temp->next = temp2;
}

60
 Cont…
 Here, the new name is passed to the appropriate function as a parameter. We'll
go through the function for adding a node to the right-most end of the list.
 The method is similar for adding a node at the other end. Firstly, a temporary
pointer is set up and is made to march along the list until it points to last node in
the list.

 After that, a new node is declared, and the name is copied into it.
 The next pointer of this new node is set to NULL to indicate that this node will
be the new end of the list.
 The prev pointer of the new node is linked into the last node of the existing list.
 The next pointer of the current end of the list is set to the new node.

61
 Deleting a Node From a Doubly Linked List

Reading Assignment

62
 Circularly Linked Lists
 In circularly linked list, the popular convention is to have the last
cell keep a pointer back to the first node.
 The last cell points to head in this case instead of NULL.
 This can be done with both singly linked lists as well as doubly
linked lists.
 This clearly affects some of the tests, but the structure is popular in
some applications.

Fig. singly and doubly linked circular linked lists

63
 Circularly Linked Lists
 Advantage is that we can start searching from any node of the
linked list and get to any other node. No logical head and tail
pointers.
 However, we follow the conventions i.e., first element inserted
into the list is given status of head and last element entered is
called as a tail.

 Some characteristics of Circular Linked list are that the Last node
references the first node, every node has a successor, and no node
in a circular linked list contains NULL.
64
 Defining a Circular Linked List
#include <iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* NodePtr;
Insert into an empty Circular Linked list
Node *loc = new Node;
loc->data = 10;
Tail = loc;
Tail->next = Tail;

65
 Insert to head of a Circular Linked List
loc->next = Tail->next;
Tail->next = loc;

Insert to end of a Circular Linked List

loc->next = Tail->next;
Tail->next = loc;
Tail = loc;

66
 Delete a node from a single-node Circular Linked List
Cur = Tail;
Tail = NULL;
delete Cur;

Delete the head node from a Circular Linked List

Cur = Tail -> next;
Tail->next = Cur->next
delete Cur;

67
 Delete the end node from a Circular Linked List
Prev->next = Tail->next;
delete Tail;
Tail = Prev;

68
 Any Question

69