CSE-281: Data Structures and Algorithms

Linked Lists
(Chapter-4)

Ref: Schaum's Outline Series, Theory and problems of Data Eftekhar Hossain
Structures
By Seymour Lipschutz Assistant Professor
Dept. of ETE, CUET
And Online Resource
1
Topics to be Covered
Difference between array and linked list
Types of Linked List
Singly Linked List
Operations on Linked list

2
Introduction
Suppose we want to arrange the name of the students according
to the first letter of their names
Mick, Jhon, Alpha, Mark, Rock , Tony
We can do this in two ways

Two Ways

Arrays Linked List

1 2 3 4 data addr data addr

3
Example
We want to store a list of numbers : 23, 44, 87, 96

23 44 87 96

1000 1004 1008 1012

Assuming size of int is 4 Bytes

In an array , elements are stored in consecutive memory locations

Array is the sequential representation of the list.

4
Example

We want to store a list of numbers : 23, 44, 87, 96

23 5000 44 4750 87 3970 96 NULL

1000 5000 4750 3970

1000

Head

Nodes are scattered here and there in memory but they are still
connected with each other.
Linked List is the link representation of List

5
Limitations of Arrays
Arrays have a fixed dimension.

Once the size of an array is decided it can not be increased or

decreased during execution.

Array elements are always stored in contiguous memory

locations.

Operations like insertion or deletion of the array are pretty

tedious.

To over come this limitations we use linked list.

6
Linked List
Linked list is a linear data structure.

It is a collection of elements called nodes.

Each node contains two parts, i.e. DATA part and LINK part.

The data contains elements and

Link contains address of another node.

Node

Data Pointer or Link

to the next Node
7
Array Vs Linked List
Array Linked List

Array is a collection of elements of Linked List is an ordered collection of

similar data type. elements of same type, which are
connected to each other using pointers.
Array supports Random Access, which Linked List supports Sequential
means elements can be accessed Access, which means to access any
directly using their index, like arr[0] for element/node in a linked list, we have to
1st element, arr[6] for 7th element etc. sequentially traverse the complete
Hence, accessing elements in an array linked list, upto that element.
is fast with a constant time complexity To access nth element of a linked list,
of O(1). time complexity is O(n).

In an array, elements are stored In a linked list, new elements can be

in contiguous memory location or stored anywhere in the memory.
consecutive manner in the memory. Address of the memory location
allocated to the new element is stored in
the previous node of linked list, hence
forming a link between the two
nodes/elements.
8
Array Vs Linked List
Array Linked List

In array, Insertion and Insertion and Deletion operations

Deletion operation takes more time, as are fast in linked list.
the memory locations are consecutive
and fixed.
Memory is allocated as soon as the Memory is allocated at runtime, as and
array is declared, at compile time. It's when a new node is added. It's also
also known as Static Memory known as Dynamic Memory
Allocation. Allocation.
In array, each element is independent In case of a linked list, each
and can be accessed using it's index node/element points to the next,
value. previous, or maybe both nodes.
Size of the array must be specified at Size of a Linked list is variable. It grows
time of array declaration. at runtime, as more nodes are added to
it.
No memory waste if the array is full or Since memory is allocated dynamically
almost full; otherwise may result in there is no waste of memory.
much memory waste.
9
Types of Linked List

Single Linked List

Double Linked List

Circular Linked List

Circular Double Linked List

10
Single Linked List (SLL)
A single linked list is one in which all the nodes are linked
together in some sequential manner .

First

23 5000 44 4750 87 3970 96 NULL

1000 5000 4750 3970

11
Circular Singly Linked List
A circular linked list is one which has no beginning and no ending.
The null pointer in the last node of a linked list is replaced with the
address of its first node such a list is called circular linked list.

First Last node contains the address of the first node

23 5000 44 4750 87 3970 96 1000

1000 5000 4750 3970

12
Double Linked List
A single linked list has some disadvantages
That it can traverse it in one direction.
Prev data Next
Many applications require searching
backward and forward travelling
A doubly linked list is divided into three parts When each node is
divided into three parts.
They are two link parts and one data part.

First Contains the address of previous node and next node

NULL 10 2000 1000 15 3000 2000 20 NULL

1000 2000 3000

13
Operations on Linked List
The basic operations on Linked lists are
Creation
Insertion
Deletion
Traversing
The creation operation is used to create a linked list.
Insertion operation is used to insert a new node in the linked list at
the specified position.
A new node may be inserted at the beginning of a linked list, at the
end of the linked list , at the specified position in a linked list.
If the list itself is empty , then the new node is inserted as a first
node.

14
Operations on Linked List
Deletion operation is used to delete on item from the linked list. It
may be deleted from the beginning of a linked list, specified
position in the list.

Traversing operation is a process of going through all the nodes of

a linked list from one end to the another end.

If we start traversing from the very first node towards the last node
, It is called forward traversing.

If the traversal start from the last node towards the first node , it is
called backward traversing.

15
Inserting a node in SLL
There are 3 cases here:-
Insertion at the beginning
Insertion at the end
Insertion after a particular node

There are two steps to be followed for inserting at the beginning:-

Make the next pointer of the node point towards the first node of the list
Make the start pointer point towards this new node
If the list is empty simply make the start pointer point towards the new node;

16
Inserting a node at beginning

17
Inserting a node at the end
Here we simply need to make the next pointer of the last node
point to the new node

18
Inserting after an element
Here we again need to do 2 steps :-

Make the next pointer of the node to be inserted point to the next node of the
node after which you want to insert the node

Make the next pointer of the node after which the node is to be inserted,
point to the node to be inserted

19
Deleting a node in SLL
Here also we have three cases:-
Deleting the first node
Deleting the last node
Deleting the intermediate node

DELETING THE FIRST NODE

Here we apply 2 steps:-
Making the start pointer point towards the 2nd node
Deleting the first node using delete keyword

20
Deleting the Last node
Here we apply 2 steps:-
Making the second last node’s next pointer point to NULL
Deleting the last node via delete keyword

21
Deleting a particular node
Here we make the next pointer of the node previous to the node
being deleted ,point to the successor node of the node to be deleted
and then delete the node using delete keyword

22
Advantages of Linked lists
We can dynamically allocate memory space as needed.

We can release the unused space in the situation where the

allocated space seems to be more.

Operation related to data elements like insertions or deletion are

more simplified.

Operation like insertion or deletion are less time consuming.

Linked lists provide flexibility in allowing the items to be arranged

efficiently.

23
Thank You

24