Lesson 7: Linked lists
7.1. Introduction
A linked list is a linear data structure which consists of collection of nodes. Each node in
the list has two components:
i. Data field- To store the values
ii.Link field-To store address to the next node
Header NULL
Header (first): Contains address to the first node. The last node points to null.
7.2. Lesson objectives
By the end of this lesson, the students should be able to:
Explain applications of a linked list
Discuss operations that can be applied on linked lists
Create and use linked lists using pointers
7.3. Lesson outline
This lesson is organized as follows:
7.1. Introduction
7.2. Lesson objectives
7.3. Lesson outline
7.4. Declaration of linked lists
7.5. Basic operations of a linked list
7.6. Applications of linked lists
7.7. Types of linked lists
7.8. Building a linked list
7.9. Revision questions
7.10. Summary
7.11. Suggested reading
7.4. Declaration of linked lists
Singly linked list: A linked list can be declared as follows: struct
node
{ int data;
node *next;
};
Doubly linked list: A doubly linked list is declared as follows:
struct doublenode
{ int data; doublenode *next;
double node *previous;
};
7.5. Basic Operations of a Linked List
Search: Operation used to search a list to determine whether a particular item is in the list.
Insert: Operation used to insert an item in the list.
Delete: An operation used to remove an item from the list
Traversing/Searching a List
Typically to traverse the list, one has to declare another pointer (temporary pointer) that
follows the same declaration as head.
-Start
-Declare two pointers first and current to point to first node
-While current is not null (end of the list) move the current to point to the next
node.
-Stop
Insertion operation
Algorithm to insert a new node into a linked list:
a) To insert a node when the list is empty
-Start
-Declare two pointers first and last.
-Create new node
-Let first and last pointers point to the new node
-Let the pointer of the new node point to null
-Stop
b) To insert a new node at the beginning of linked list.
-Start
-Declare two pointers first and last.
-Create new node
-Let the pointer of the new node point to first
-Update first to point to the new node
-Stop
c) To insert the node at the mid position of the linked list.
-Start
-Create new node
-Create a pointer to point to the position immediately before the insertion point.
-Set the link of the new node to point to the next node (node after the new
node).
-Update the link of the node before the new node to point to new node.
-Stop
d) To insert a node at the last position of the linked list.
-Start
-Create new node
-Declare first and last pointers - Let the last pointer to new node.
-Update the link of the new node to point to NULL - Update the last node’s
pointer to point to the new node. - Stop
Delete operation
a)Delete a node when a linked list has only one node.
-Start
-Declare two pointers first and last.
-Assign first and last pointers to NULL
-Delete the node
-Stop
b) Delete a node from the beginning of the linked list.
-Start
-Declare temporary pointer to point to first - Move the first pointer to point to
next element - Set temporary pointer to NULL.
-Stop
c)Delete a node from a mid position of the linked list.
-Start
-Declare a traversing pointer (trpointer) to point to the node before the node to
delete.
-Declare a temporary pointer(temp) to point to the node to delete.
-Update the pointer of the node before the node to delete to point to the node
after the node to delete.
-Let the pointer of the node to delete point to null.
-Set temporary pointer to NULL.
-Delete the node from the memory.
-Stop
7.6. Applications of linked lists
They are used to implement other complex data structures like queues and stacks. They
can be used in file management in operating systems. Linked lists can also be used in
dynamic memory management i.e. allocating and releasing memory at run time.
7.7. Types of Linked List
a) Singly or Chain Linked List.
b)Doubly or Two Way Linked List.
c) Circular Linked List.
d)Circular Doubly Linked List.
Doubly Linked Lists
A doubly linked list is a linked list that every node has its “next” and “previous” node
stored.
Advantage
The advantage of a doubly linked list is that it can be traversed in any direction, which can
be beneficial when performing iterations on the list.
Disadvantages
Complexity when performing other operations search as delete and insert.
Extra pointers require more memory to store.
Circular Linked Lists
A circular linked list is one where the first node points to the last node of the list.
Advantage.
It is easier to traverse the linked list even after reaching the last node.
Disadvantages.
It is not easy to reverse the linked list.
The problem of infinite loop can occur.
Traversal is one way
Remark: Declaration is similar to singly linked list. However last node does not point to
null.
7.8. Building a Linked List
There are two main ways to build a linked list, forward and backward.
Simple program to implement list ADT
i. Write a program in c++ to build a singly list.
struct node
{
float num;
node *next;
};
int main()
{
node *first,*temp1,*temp2, *last; first=new node;
cout<<"Please enter the value of the first node: "<<endl;
cin>>first->num;
first->next;
temp1=new node; cout<<"Please enter the value of the
second node: "<<endl; cin>>temp1->num; temp1->next;
temp2=new node; cout<<"Please enter the value of the third
node: "<<endl; cin>>temp2->num; temp2->next; last=new
node; cout<<"Please enter the value of the fourth node:
"<<endl; cin>>last->num;
cout<<"The values are :"<<endl; cout<<first->num<<" : "<<temp1-
>num<<": "<<temp2->num<<": "<<last-
>num<<endl; last->next=0;
return 0;
}
7.9. Revision questions.
a) Briefly describe the following types of lists:
i. Doubly linked lists
ii. Circular linked list
iii.Singly linked list
b)Describe any two operations performed on linked list ADT
c) Write an algorithm to create a singly linked list to store the elements 2,4,2,6,7 and 11 in
that order.
d)Implement the algorithm above using c++.
7.10. Summary
In this lesson have learnt that a linked list is a linear data structure that consists of set of
nodes where each node stores link to the next node and data item. A linked list can be
implemented using structures and classes. Some of the applications of linked list include
implementation of other complex data structures, file management and memory
management. Linked lists are classified as singly linked lists, circular linked lists and
doubly linked lists. The operations performed on linked lists include traverse, insert, delete
and search.
7.11. Suggested reading
[1]. Data structures using C and C++, 2nd Edition by Yedidyah Langsam, Aaron
J.Augenstein and Aaron M.Tenebaum: Publisher: Pearson.
[2]. Data structures and algorithms in c++ by Michael T.Goodrich, Robertio Tamassia and
David Mount: Publisher: Wiley
[3]. Fundamentals of data structures in c++ by Ellis Horowitz, Sartaj Sahni and Dinesh
Mehta. Publisher:Galgotia
[4]. Introduction to data structures and algorithms with c++ by Glenn W.Rowe . Publisher:
Prentice Hall.
