D ata S tructures
Chapter 2: Linked Lists
Asmelash Girmay
Department of Information Technology
2.1 Introduction
• If a memory is allocated for a variable during the compilation (i.e. before
execution) of a program, then it is fixed and cannot be changed.
• For Example: an array A[20] is declared with 20 elements, then the allocated
memory is fixed and cannot decrease or increase 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.
Oct 01, 2019 IT3201 Data Structures 2
2.2 Definition of Linked List
• 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 element, and
the second part contains the address part of the next node in the linked list.
• Address part of the node is also called linked or next field.
• Note:
• The arrow is drown from the address part 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.
• i.e. NULL pointer indicates the end of the linked list.
• START pointer will hold the address of the first node in the list START=NULL if there is no list (i.e. NULL list or
empty list).
Oct 01, 2019 IT3201 Data Structures 3
2.2 Definition of Linked List …
Oct 01, 2019 IT3201 Data Structures 4
2.3 Representation of Linked List
• Suppose we want to store a list of integer numbers using linked list. Then it can
be schematically represented as:
• The linear linked list can be represented in memory with the following declaration.
Oct 01, 2019 IT3201 Data Structures 5
2.4 Advantages and Disadvantages
• Advantages:
1. Are dynamic data structure: i.e., they can grow or shrink during the execution of the 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.
• Disadvantages:
1. More memory: to store an integer number, a node with integer data and address field is allocated.
That is more memory space is needed.
2. Access to an arbitrary data item is little bit cumbersome and also time consuming.
Oct 01, 2019 IT3201 Data Structures 6
2.5 Operations on Linked List
• The primitive operations performed on the linked list are as follows
1. Creation
2. Insertion
3. Deletion
4. Traversing
5. Searching
6. 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.
Oct 01, 2019 IT3201 Data Structures 7
2.5 Operations on Linked List …
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
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
Oct 01, 2019 IT3201 Data Structures 8
2.5 Operations on 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, nodes 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
Oct 01, 2019 IT3201 Data Structures 9
2.6 Type of Linked List
• Basically we can divide the linked list into the following three types in
the order in which they (or node) are arranged.
1. Singly linked list
2. Doubly linked list
3. Circular linked list
Oct 01, 2019 IT3201 Data Structures 10
2.6.1 Singly Linked List [SLL]
• All the nodes in a singly linked list are arranged sequentially linked by a pointer.
• A singly linked list can grow or shrink, because it is a dynamic data structure.
Oct 01, 2019 IT3201 Data Structures 11
2.6.1 Singly Linked List…
Oct 01, 2019 IT3201 Data Structures 12
2.6.1 Singly Linked List…
• Algorithm for Inserting a Node
• Insertion of New Node Suppose START is the first position in linked list.
• Let DATA be the element to be inserted in the new node.
• POS is the position where the new node is to be inserted.
• TEMP is a temporary pointer to hold the node address.
Oct 01, 2019 IT3201 Data Structures 13
2.6.1 Singly Linked List…
• Algorithm for Inserting a Node…
Oct 01, 2019 IT3201 Data Structures 14
2.6.1 Singly Linked List…
• Algorithm for Inserting a Node…
Insert a Node at the end
1. Input DATA to be inserted
2. Create a NewNode
3. NewNode → DATA = DATA
4. NewNode → Next = NULL
5. If (SATRT equal to NULL)
(a) START = NewNode
6. Else
(a) TEMP = START
(b) While (TEMP → Next not equal to NULL)
(i) TEMP = TEMP → Next
7. TEMP → Next = NewNode
8. Exit
Oct 01, 2019 IT3201 Data Structures 15
2.6.1 Singly Linked List…
• Algorithm for Inserting a Node…
Oct 01, 2019 IT3201 Data Structures 16
2.6.1 Singly Linked List…
• Algorithm for Deleting a Node
Oct 01, 2019 IT3201 Data Structures 17
2.6.1 Singly Linked List…
• Algorithm for Deleting a Node…
• Suppose START is the first position in linked list.
Let DATA be the element to be deleted.
TEMP, HOLD is a temporary pointer to hold the
node address.
Oct 01, 2019 IT3201 Data Structures 18
2.6.1 Singly Linked List…
• Algorithm for searching a Node
• Suppose START is the address of the first node in the linked list and DATA is the information to be
searched. After searching, if the DATA is found, POS will contain the corresponding position in the
list.
Oct 01, 2019 IT3201 Data Structures 19
2.6.1 Singly Linked List…
• Algorithm for Traversing the Linked List
• Suppose START is the address of the first node in the linked list.
• Following algorithm will visit all nodes from the START node to the end.
Implementation of Singly linked list – LAB#2
Oct 01, 2019 IT3201 Data Structures 20
2.6.1 Applications SLL
• Singly linked list is used in:
• Implementation of dynamic Stacks
• Implementation of dynamic Queue
• Representation of polynomial functions
Oct 01, 2019 IT3201 Data Structures 21
2.6.1 Applications SLL: Polynomial
• Different operations, such as addition, subtraction, division and multiplication of polynomials can
be performed using linked list.
• In this section, we discuss about polynomial addition using linked list.
• Consider two polynomials f(x) and g(x); it can be represented using linked list as follows in Fig.
Oct 01, 2019 IT3201 Data Structures 22
2.6.2 Doubly Linked List [DLL]
• A doubly linked list is one in which all nodes are linked together by
multiple links which help in accessing both the successor (next) and
predecessor (previous) node for any arbitrary node within the list.
• Every nodes in the doubly linked list has three fields:
• Left Pointer, Right Pointer and DATA. The following fig. shows a typical doubly
linked list.
Oct 01, 2019 IT3201 Data Structures 23
2.6.2 Doubly Linked List…
• LPoint will point to the node in the left side (or previous node) that is LPoint will
hold the address of the previous node.
• RPoint will point to the node in the right side (or next node) that is RPoint will
hold the address of the next node. DATA will store the information of the node.
Oct 01, 2019 IT3201 Data Structures 24
2.6.2 Doubly Linked List Representation
• A node in the doubly linked list can be represented in memory with the following
declarations.
• All the operations performed on singly linked list can also be performed on doubly linked
list. See the ff. insertion and deletion of nodes.
Oct 01, 2019 IT3201 Data Structures 25
2.6.2 Doubly Linked List Representation…
Implementation of Doubly linked list – LAB#3
Oct 01, 2019 IT3201 Data Structures 26
2.6.2 Doubly Linked List Algorithms
• Algorithm for Inserting a Node
• Suppose START is the first position in linked list.
• Let DATA be the element to be inserted in the new node.
• POS is the position where the NewNode is to be inserted.
• TEMP is a temporary pointer to hold the node address.
Oct 01, 2019 IT3201 Data Structures 27
2.6.2 Doubly Linked List Algorithms…
• Algorithm for Inserting a Node…
Oct 01, 2019 IT3201 Data Structures 28
2.6.2 Doubly Linked List Algorithms…
• Algorithm for Deleting a Node
• Suppose START is the address of the first node in the linked list.
• Let POS is the position of the node to be deleted.
• TEMP is the temporary pointer to hold the address of the node.
• After deletion, DATA will contain the information on the deleted node.
Oct 01, 2019 IT3201 Data Structures 29
2.6.2 Doubly Linked List Algorithms…
• Algorithm for Deleting a Node…
Oct 01, 2019 IT3201 Data Structures 30
2.6.3 Circular Linked List [CLL]
• A circular linked list is one, which has no beginning and no end.
• A singly linked list can be made a circular linked list by simply storing the address
of the very first node in the linked field of the last node.
Implementation of Circular linked list – LAB#3
Oct 01, 2019 IT3201 Data Structures 31
2.6.3 Circular Linked List …
• A circular doubly linked list has both the successor pointer and
predecessor pointer in circular manner as shown below.
Oct 01, 2019 IT3201 Data Structures 32
The End ☺
