P a g e | 46

Linear Data Structure-III:

Linked-List

A list is a fundamental abstract data type used in computer science to store a collection of elements. It
allows for the organization and manipulation of data in a sequential manner. Lists can be implemented
using various data structures, with one of the most common implementations being linked lists.

A linked list is a data structure consisting of a sequence of elements called nodes. Each node contains
both data and a reference (or pointer) to the next node in the sequence. The last node typically points
to null, indicating the end of the list. Linked lists offer dynamic memory allocation, allowing for efficient
insertion and deletion operations anywhere in the list.

Figure : Types of Linked List

Linked lists are broadly categorized into several types:

 Singly Linked List:

o Each node contains data and a reference to the next node.
o Traversal is only possible in one direction, from the head (the first node) to the end of
the list.
 Doubly Linked List:
o Each node contains data, a reference to the next node, and a reference to the previous
node.
o Traversal is possible in both forward and backward directions, offering greater flexibility
but requiring more memory for storing additional pointers.

Lecture Notes: “Data Structures and Algorithms”,

for more details Contact Dr. Atul Nandwal-9229696960
 P a g e | 47

 Circular Linked List:

o In a singly circular linked list, the last node points back to the first node, forming a
circular structure.
o In a doubly circular linked list, both the first and last nodes point to each other, creating
a circular structure with bidirectional traversal.
 Sorted Linked List:
o Nodes are arranged in sorted order based on a specific criterion (e.g., numerical or
alphabetical order).
o Insertion and deletion operations maintain the sorted order of the list, ensuring efficient
searching.

Linked lists provide several advantages, including dynamic memory allocation, efficient insertion and
deletion operations (especially at the beginning and middle of the list), and flexibility in size. However,
they also have drawbacks such as slower access times for random element retrieval compared to
arrays and additional memory overhead due to the storage of pointers. The choice of linked list type
depends on factors such as the specific requirements of the application and the desired trade-offs
between efficiency and memory usage.

Linked List Represent through stack

Yes, we can use a linked list to represent a stack. In fact, linked lists are one of the most common
implementations for stacks due to their dynamic memory allocation and efficient insertion and deletion
operations, which align well with the operations required for a stack.

In a linked list-based implementation of a stack, each element of the stack is represented by a node in
the linked list. The top of the stack corresponds to the head (or front) of the linked list.

Linked list can be used to represent a stack:

 Push Operation: To push an element onto the stack, we simply add a new node to the
beginning of the linked list, making it the new head of the list.
 Pop Operation: To pop an element from the stack, we remove the node at the beginning
of the linked list, returning its value as the popped element.

Lecture Notes: “Data Structures and Algorithms”,

for more details Contact Dr. Atul Nandwal-9229696960
 P a g e | 48

 Peek Operation: To peek at the top element of the stack without removing it, we simply
return the value of the head node of the linked list.
 isEmpty Operation: To check if the stack is empty, we can simply check if the linked
list is empty by examining if the head node is null.

Since linked lists allow for efficient insertion and deletion operations at the beginning of the list, they are
well-suited for implementing stacks. Additionally, linked lists can dynamically grow and shrink in size as
elements are pushed and popped from the stack, making them flexible and efficient for stack
operations.

Dynamically Linked through Stacks

"Dynamically Linked Stacks" refer to a stack data structure implemented using a dynamically allocated
linked list. In this context, "dynamically linked" indicates that the stack is implemented using a linked list
where nodes are allocated dynamically as needed during runtime.

In a dynamically linked stack:

 Nodes: Each element of the stack is represented by a node in the linked list. Each node
typically contains two components:
o Data: The actual value or payload of the element.
o Pointer: A reference or link to the next node in the linked list.
 Dynamic Allocation: Nodes are dynamically allocated from the heap memory as
elements are pushed onto the stack. This allows the stack to grow and shrink in size
dynamically based on the number of elements it contains.
 Efficient Push and Pop Operations: Since linked lists support efficient
insertion and deletion operations at the beginning of the list, pushing and popping elements
from a dynamically linked stack can be performed in constant time (O(1)).
 Flexibility: Dynamically linked stacks can efficiently handle variable numbers of elements
without the need for preallocation of memory. This flexibility makes them suitable for
applications where the size of the stack may vary unpredictably during program execution.
 Memory Management: Proper memory management is essential in dynamically
linked stacks to ensure that memory allocated for unused nodes is deallocated to prevent
memory leaks.

Lecture Notes: “Data Structures and Algorithms”,

for more details Contact Dr. Atul Nandwal-9229696960
 P a g e | 49

Overall, dynamically linked stacks combine the flexibility of linked lists with the efficient stack
operations, providing an effective data structure for managing data in a Last In, First Out (LIFO)
manner.

Representation of Queue through Linked List

Yes, we can use a linked list to represent a queue. While arrays are often used for implementing
queues due to their simplicity and efficient random access, linked lists offer advantages in certain
scenarios, particularly when the size of the queue is dynamic and unpredictable.

In a linked list-based implementation of a queue, each element of the queue is represented by a node
in the linked list. The front of the queue corresponds to the head (or first) node of the linked list, and the
rear of the queue corresponds to the tail (or last) node of the linked list.

Here's how a linked list can be used to represent a queue:

 Enqueue Operation: To enqueue an element into the queue, we add a new node to the end of
the linked list, updating the rear pointer to point to the newly added node.
 Dequeue Operation: To dequeue an element from the queue, we remove the node at the front
of the linked list, updating the front pointer to point to the next node in the list.

 Peek Operation: To peek at the front element of the queue without removing it, we simply
return the value of the head node of the linked list.

 isEmpty Operation: To check if the queue is empty, we can simply check if the linked list is
empty by examining if the head node is null.

Since linked lists allow for efficient insertion and deletion operations at both the beginning and end of
the list, they are well-suited for implementing queues. Additionally, linked lists can dynamically grow
and shrink in size as elements are enqueued and dequeued from the queue, making them flexible and
efficient for queue operations. However, it's important to note that in a singly linked list implementation,
dequeueing elements from the front of the list may require traversing the entire list, resulting in linear

Lecture Notes: “Data Structures and Algorithms”,

for more details Contact Dr. Atul Nandwal-9229696960
 P a g e | 50

time complexity (O(n)). To improve dequeue efficiency, a doubly linked list or a circular linked list can
be used.

Dynamically Linked Queues

Dynamically linked queues are a type of queue data structure implemented using a dynamically
allocated linked list. In this context, "dynamically linked" indicates that the queue is implemented using
a linked list where nodes are allocated dynamically as needed during runtime.
In a dynamically linked queue:
 Nodes: Each element of the queue is represented by a node in the linked list. Each node
typically contains two components:
o Data: The actual value or payload of the element.
o Pointer: A reference or link to the next node in the linked list.
 Dynamic Allocation: Nodes are dynamically allocated from the heap memory as
elements are enqueued into the queue. This allows the queue to grow and shrink in size
dynamically based on the number of elements it contains.
 Efficient Enqueue and Dequeue Operations: Since linked lists support
efficient insertion at the end and removal from the front, enqueuing and dequeuing elements
from a dynamically linked queue can be performed in constant time (O(1)).
 Flexibility: Dynamically linked queues can efficiently handle variable numbers of elements
without the need for preallocation of memory. This flexibility makes them suitable for
applications where the size of the queue may vary unpredictably during program execution.
 Memory Management: Proper memory management is essential in dynamically
linked queues to ensure that memory allocated for unused nodes is deallocated to prevent
memory leaks.
 Implementation Choices: Depending on the specific requirements and
performance considerations, different types of linked lists such as singly linked lists, doubly
linked lists, or circular linked lists can be used to implement dynamically linked queues.

Overall, dynamically linked queues combine the flexibility of linked lists with efficient queue operations,
providing an effective data structure for managing data in a First In, First Out (FIFO) manner.

Linked Lists are different from Arrays and Dynamic Arrays

Lecture Notes: “Data Structures and Algorithms”,

for more details Contact Dr. Atul Nandwal-9229696960
 P a g e | 51

Linked lists, arrays, and dynamic arrays are all data structures used for storing collections of elements,
but they differ in their underlying implementations, characteristics, and performance characteristics.
Linked Lists:
o In a linked list, elements are stored in dynamically allocated nodes, each containing a
data element and a pointer/reference to the next node in the sequence.
o Linked lists support dynamic memory allocation and can grow or shrink in size as
needed.
o Insertion and deletion operations in linked lists are generally efficient, especially at the
beginning and middle of the list, as they involve updating pointers rather than shifting
elements.
o Traversal of a linked list requires following pointers from one node to the next, which
can result in slower access times compared to arrays due to the lack of contiguous
memory allocation.
o Common types of linked lists include singly linked lists, doubly linked lists, and circular
linked lists.
Arrays:
o Arrays are static data structures that store elements in contiguous memory locations.
o Arrays have fixed sizes determined at compile time, and their sizes cannot be changed
dynamically during runtime.
o Accessing elements in an array is efficient, especially random access, as elements are
stored contiguously, allowing for constant-time access based on the element's index.
o Insertion and deletion operations in arrays, especially in the middle, can be inefficient
as they require shifting elements to accommodate changes in size or position.
o Arrays are suitable for applications where fast random access and fixed-size storage
are required.

Dynamic Arrays:
o Dynamic arrays, also known as resizable arrays or ArrayLists in some programming
languages, are similar to arrays but support dynamic resizing.
o Dynamic arrays allocate memory in blocks, and when the capacity of the array is
exceeded, a new, larger block of memory is allocated, and the elements are copied
over.

Lecture Notes: “Data Structures and Algorithms”,

for more details Contact Dr. Atul Nandwal-9229696960
 P a g e | 52

o Dynamic arrays combine the flexibility of linked lists with the efficient access times of
arrays, providing amortized constant-time access for appending elements and efficient
random access.
o Insertion and deletion operations in dynamic arrays can be efficient, especially at the
end of the array, but may require occasional resizing, resulting in occasional
performance hits.
o Dynamic arrays are widely used in practice due to their versatility and efficiency in a
wide range of applications.

linked lists, arrays, and dynamic arrays each have their own strengths and weaknesses, and
the choice of data structure depends on the specific requirements of the application, including
the type of operations performed, memory considerations, and performance requirements.

Lecture Notes: “Data Structures and Algorithms”,

for more details Contact Dr. Atul Nandwal-9229696960