Data Structures

Batch_16 _4 semester

th

CS + IT+ IS Departments




Lecture 2: Linked List Data Structure

By: Hind Ali

linked list
A linked list is a linear data structure, in which
elements are not stored at a contiguous location,
rather they are linked using pointers.
Linked List forms a series of connected nodes,
where each node stores the data and the address
of the next node.
Node Stru c tu re: A n ode in a lin ked list
typically consists of two components:
 Data: It holds the actual value or data associated
with the node.
 Next Pointer: It stores the memory address
(reference) of the next node in the sequence.
 Head and Tail: The linked list is accessed through
the head node, which points to the f ir st node in
the list. The last node in the list points to NULL or
nullptr, indicating the end of the list. This node is
known as the tail node.
Importance of Linked List


Here are a few advantages of a linked list that is listed
below, it will help you understand why it is necessary to
know:
• Dynamic Data structure: The size of memory can be
allocated or de-allocated at run time based on the
operation insertion or deletion.
• Ease of Insertion/Deletion: The insertion and deletion
of elements are simpler than arrays since no elements
need to be shifted after insertion and deletion, Just the
address needed to be updated.
• Efficient Memory Utilization: As we know Linked List is
a dynamic data structure the size increases or
decreases as per the requirement so this avoids the
wastage of memory.
• Implementation: Various advanced data structures can
be implemented using a linked list like a stack, queue,
graph, hash maps, etc
List Using Linked Memory
Why Linked List?
• Arrays can be used to store linear data of similar types,
but arrays have the following limitations:
– The size of the arrays is fixed.
– Insertion of a new element / Deletion of a existing
element in an array of elements is expensive.
Advantages of Linked Lists over arrays:
1. Dynamic Size: Linked lists can grow or shrink dynamically,
as memory allocation is done at runtime.
2. Insertion and Deletion: Adding or removing elements from
a linked list is efficient, especially for large lists.
3. Flexibility: Linked lists can be easily reorganized and
modified without requiring a contiguous block of memory.
List Using Linked Memory

• Disadvantages of Linked Lists

1. Random Access: Unlike arrays, linked lists do not allow
direct access to elements by index. Traversal is
required to reach a specific node.
2. Extra Memory: Linked lists require additional memory
for storing the pointers, compared to arrays.
List Using Linked Memory

 Various cells of memory are not allocated

consecutively in memory.
 With arrays, the second element was right next
to the first element.
 Now the first element must explicitly tell us
where to look for the second element.
 Do this by holding the memory address of the
second element
Linked List
 Create a structure called a Node.

object next

 The object field will hold the actual list element.

 The next field in the structure will hold the
starting location of the next node.
 Chain the nodes together to form a linked list.
 Linked List
 Picture of our list (2, 6, 7, 8, 1) stored as a
linked list:

head

2 6 8 7 1 size=5

current
Linked List
Note some features of the list:
 Need a head to point to the first node of the list.
Otherwise we won’t know where the start of the
list is.
 The current here is a pointer, not an index.
 The next field in the last node points to nothing.
We will place the memory address NULL which
is guaranteed to be inaccessible.
 Linked List
 Actual picture in memory:
1051 6
1052 1063
current 1053 1063
1054 2
head 1055 1051
1056
2 6 8 7 1 1057 7
1058 1060
current 1059
1060 1
1061 0
head 1062 1054
1063 8
1064 1057
1065
 Types of Linked Lists:

 There are mainly three types of linked lists:

1. Single-linked list
2. Double linked list
3. Circular linked list
Single-linked list

• In a singly linked list, each node contains a
reference to the next node in the sequence.
Traversing a singly linked list is done in a
forward direction.
// Define the Node structure
struct Node {
int data;
Node* next;

Node(int value) {
data = value;
next = nullptr;
}
};
Double linked list


In a doubly linked list, each node contains references to both
the next and previous nodes. This allows for traversal in both
forward and backward directions, but it requires additional
memory for the backward reference.
Doubly-linked List
 Moving forward in a singly-linked list is easy;
moving backwards is not so easy.
 To move back one node, we have to start at the
head of the singly-linked list and move forward
until the node before the current.
 To avoid this we can use two pointers in a node:
one to point to next node and another to point
to the previous node:

prev element next

Doubly-linked List
 Need to be more careful when adding or
removing a node.
 Consider add: the order in which pointers are
reorganized is important:

head 2 6 8 7 1 size=5

current
// Define the Node structure in DLL
struct Node {
int data;
Node* next;
Node* prev;

Node(int x) {
data = x;
next = nullptr;
prev = nullptr;
}
};
Circular linked list

• In a circular linked list, the last node points back
to the head node, creating a circular structure. It
can be either singly or doubly linked.
Circularly-linked lists
 A circular linked list is either a singly or doubly linked
list in which there are no NULL values. Here, we can
implement the Circular Linked List by making the use of
Singly or Doubly Linked List. In the case of a singly
linked list, the next of the last node contains the
address of the f irst node and in case of a doubly-linked
list, the next of last node contains the address of the
f ir st node and prev of the f ir st node contains the
address of the last node.
 The next f ie ld in the last node in a singly-linked list is
set to NULL.
 Moving along a singly-linked list has to be done in a
watchful manner.
 Doubly-linked lists have two NULL pointers: prev in the
first node and next in the last node.
 A way around this potential hazard is to link the last
node with the f irst node in the list to create a circularly-
linked list.
 Cicularly Linked List
 Two views of a circularly linked list:
current

head 2 6 8 7 1 size=5

current
6
8
size=5
head 2

1
Basic operation of Linked Lists:


• Initialization: A linked list can be initialized by creating a
head node with a reference to the f ir st node. Each
subsequent node contains a value and a reference to the
next node.
• Insertion: Adding a new node to a linked list involves
adjusting the pointers of the existing nodes to maintain
the proper sequence. Insertion can be performed at the
beginning, end, or any position within the list
• Deletion: Removing a node from a linked list requires
adjusting the pointers of the neighboring nodes to bridge
the gap left by the deleted node. Deletion can be
performed at the beginning, end, or any position within
the list.
• Searching :Searching for a specif ic value in a linked list
involves traversing the list from the head node until the
value is found or the end of the list is reached.
• Display − Displays the complete list.


Creating a list

















// Definition of a Node in a singly linked list

struct Node {

// Data part of the node

int data;

// Pointer to the next node in the list

Node* next;
};
// head pointer point first node
Node * head=nullptr;
Linked List Insertion Operation


Algorithm Steps for the Insertion:

Display function:

Drive code (Main):

Insert function in C++
Display function
Main function
Insertion at Beginning
In this operation, we are adding an element at the
beginning of the list.
Insertion at Ending
• we are adding an element at the ending of the
list.
We will traverse the list until we f ind the last
node. Then we insert the new node to the end of
the list. Note that we have to consider special
cases such as list being empty.

In case of a list being empty, we will return the

updated head of the linked list because in this
case, the inserted node is the f irst as well as the
last node of the linked list.
Insertion at a Given Position
We are given the reference to a node, and the new node is inserted
after the given node.
Linked List - Deletion Operation
• To delete a node from a linked list, we need to do these
steps
• Find the previous node of the node to be deleted.
• Change the next pointer of the previous node
• Free the memory of the deleted node.
• In the deletion, there is a special case in which the first
node is deleted. In this, we need to update the head of
the linked list.
Deletion at Beginning
In
this deletion operation of the linked, we are deleting an
element from the beginning of the list. For this, we point
the head to the second node.
Deletion at Ending
In this deletion operation of the linked, we are
deleting an element from the ending of the list.
Search
Searching for an element in the list using a
key element. This operation is done in the
same way as array search; comparing every
element in the list with the key element
given.
END