[UNIT 3] Linked list [7 Hours]

Concept of linked organization, singly and doubly linked list and dynamic storage management,
circular linked list, operations such as insertion, deletion, concatenation, traversal of linked list,
dynamic memory management, garbage collection.

Linked Organization in Data Structure

Linked Organization is a type of data organization where elements (also known as nodes) are
not stored contiguously in memory but are linked to each other using pointers. Each element of
a linked structure contains the data and a reference (pointer) to the next element, making it
possible to traverse the data even if it is scattered throughout the memory.

Key Concepts:

1. Node: A node is the fundamental building block of a linked organization. A node typically
consists of two parts:

Data part: This stores the actual information.

Pointer part: This contains the address (or reference) to the next node in the sequence.

2. Types of Linked Lists:

Linked organization can be implemented in various ways depending on the number of pointers
in each node and the way the nodes are connected:

Singly Linked List (SLL): Each node contains a single pointer that points to the next node. The
last node in the list points to null (or None), indicating the end of the list.

[data | next] -> [data | next] -> ... -> null

Doubly Linked List (DLL): Each node contains two pointers: one pointing to the next node and
another pointing to the previous node, allowing traversal in both directions.

null <- [prev | data | next] <-> [prev | data | next] <-> ... -> null

Circular Linked List (CLL): The last node in a circular linked list points back to the first node,
creating a loop in the structure. This can be implemented as a singly or doubly linked list.

Circular Singly Linked List:

[data | next] -> [data | next] -> ... -> [data | next] -> (back to
the first node)

Circular Doubly Linked List:

(circular links exist in both directions)

3. Key Operations:

Insertion: Inserting a new node into a linked list involves:

Adjusting pointers of the adjacent nodes to accommodate the new node.

Updating the pointer of the new node to link it correctly. Insertion can occur at the beginning,
middle, or end of the list.

Deletion: Deletion involves:

Removing the node by updating the pointers of adjacent nodes to bypass the node to be
deleted.

Freeing the memory occupied by the deleted node.

Special care is taken when deleting the first or last node.

Traversal: Traversal is the process of visiting each node in the list. For a singly linked list,
traversal starts from the head (first node) and moves sequentially to the next nodes until
reaching null. In doubly and circular linked lists, traversal can be done in both directions.

4. Advantages of Linked Organization:

Dynamic Size: Unlike arrays, linked lists can grow and shrink dynamically, allowing efficient
memory utilization.

Ease of Insertion/Deletion: Adding or removing elements is generally more efficient in a linked

list compared to arrays because it does not require shifting elements.

Flexible Memory Allocation: Linked lists do not require contiguous memory allocation, making
them more adaptable in environments with limited memory.

5. Disadvantages of Linked Organization:

Memory Overhead: Each node requires extra memory for storing pointers, leading to a higher
memory overhead compared to arrays.

Random Access Not Possible: Linked lists do not allow direct access to elements based on
index; elements can only be accessed sequentially.

Complexity in Implementation: Linked structures are generally more complex to implement than
arrays because of the need to manage pointers carefully.

Applications of Linked Organization:

1. Implementation of Stacks and Queues: Linked lists provide efficient implementations for
stacks and queues by allowing dynamic growth and shrinkage without the need for resizing (as
in arrays).

2. Representation of Sparse Matrices: Linked lists are used to represent sparse matrices where
most of the elements are zero, avoiding the need to store all elements.

3. Graph Representation: Linked structures like adjacency lists are commonly used to represent
graphs efficiently, especially when the graph is sparse.

4. Dynamic Memory Allocation: Memory management schemes like heap memory often use
linked structures to track free memory blocks.

5. Polynomial Representation: Linked lists are used to represent and manipulate polynomials
where each node stores a term of the polynomial.

singly and doubly linked list

Singly Linked List (SLL)

A Singly Linked List (SLL) is a linear data structure where each node points to the next node in
the sequence, and the last node points to null. It consists of a sequence of nodes, with each
node containing two parts:

Data: Holds the actual value or data.

Pointer: Contains the address of the next node in the list.

Key Properties:
1. Head Node: The first node in the list, often referred to as the head, is the entry point to the
list.

2. Tail Node: The last node in the list, which points to null, signifying the end of the list.

3. Unidirectional Traversal: Traversal is only possible in one direction, from the head to the last
node.

Singly Linked List

Operations in Singly Linked List:

1. Insertion:

At the Beginning: A new node is inserted before the head, and the head pointer is updated to
this new node.

At the End: The new node is inserted after the current tail node, and the next pointer of the tail
node is updated to the new node.

At a Specific Position: Inserting at a given position requires traversing to that position and
updating the pointers of adjacent nodes.

2. Deletion:

From the Beginning: The head node is removed by making the second node the new head.

From the End: Deletion from the end requires traversing to the second-to-last node and
updating its next pointer to null.

From a Specific Position: Similar to insertion, deletion requires traversal to the node before the
target node, updating its pointer to bypass the target node.

3. Traversal:

Traversing through the list involves starting from the head node and following the next pointers
until the null is reached.
Advantages of Singly Linked List:

Dynamic Size: Can grow or shrink in size based on the number of elements.

Efficient Insertions and Deletions: Insertion and deletion operations (at the head or tail) are
efficient, requiring minimal changes to pointers.

Disadvantages of Singly Linked List:

No Backward Traversal: It is not possible to traverse backward since each node only has a
pointer to the next node.

More Memory: Requires extra memory for storing the pointer to the next node.

Doubly Linked List (DLL)

A Doubly Linked List (DLL) is a type of linked list in which each node contains two pointers:

Data: Holds the actual value or data.

Next Pointer: Contains the address of the next node in the sequence.

Previous Pointer: Contains the address of the previous node, allowing traversal in both
directions.

Doubly Linked List

Node Structure of Doubly Linked List

Key Properties:
1. Head Node: The first node in the list, which has its previous pointer set to null.

2. Tail Node: The last node in the list, which has its next pointer set to null.

3. Bidirectional Traversal: Nodes can be traversed in both forward and backward directions.

Operations in Doubly Linked List:

1. Insertion:

At the Beginning: A new node is inserted before the head, with its next pointer pointing to the
current head, and the head’s previous pointer updated to this new node.

At the End: A new node is inserted after the current tail node, and both the previous and next
pointers are updated accordingly.

At a Specific Position: Insertion at a given position involves updating both the next and previous
pointers of adjacent nodes.

2. Deletion:

From the Beginning: The head node is removed by updating the head to the next node and
setting the new head's previous pointer to null.

From the End: The tail node is removed by updating the previous node's next pointer to null.

From a Specific Position: Similar to insertion, deletion involves adjusting both next and previous
pointers to bypass the node to be deleted.

3. Traversal:

Forward Traversal: Starts from the head and moves in the forward direction using the next
pointer.

Backward Traversal: Starts from the tail and moves in the backward direction using the previous
pointer.

Advantages of Doubly Linked List:

Bidirectional Traversal: Allows traversal in both forward and backward directions, which is more
flexible than singly linked lists.
Efficient Deletion: Deleting a node in the middle is more efficient as we can traverse the list in
either direction to reach the node faster.

Disadvantages of Doubly Linked List:

More Memory Overhead: Each node requires additional memory for storing the previous pointer.

Complexity in Implementation: Operations such as insertion and deletion require more pointer
adjustments compared to singly linked lists.

Singly and Doubly Linked Lists – Algorithms

1. Singly Linked List (SLL)

A Singly Linked List (SLL) is a type of linked list where each node has two components:

Data part: Stores the data.

Pointer (or link) part: Stores the address of the next node.

The last node’s pointer is set to null, indicating the end of the list.

Singly Linked List

Structure of a Singly Linked List Node:

struct Node {
int data;
struct Node* next;
// Pointer to the next node
};

Operations on a Singly Linked List:

1. Insertion into a Singly Linked List

At the beginning:

A new node is created.

The new node’s next pointer is set to the current head.

The head is updated to point to the new node.

Algorithm:

def insert_at_beginning(head, data):

new_node = Node(data) # Create new node
new_node.next = head # Point new node's next to
current head
head = new_node # Update head to the new node
return head # Return updated head

At the end:

Traverse the list until the last node is found.

Create a new node and link the last node's next pointer to the new node.

Set the new node's next pointer to null.

Algorithm:

def insert_at_end(head, data):

new_node = Node(data) # Create new node
if head is None: # If list is empty
head = new_node
return head
last = head
while last.next is not None: # Traverse to the last node
last = last.next
last.next = new_node # Link last node to the new node
return head

At a given position:
Traverse the list to the desired position.

Insert the new node by adjusting the next pointers of adjacent nodes.

Algorithm:

def insert_at_position(head, position, data):

new_node = Node(data)
if position == 1: # Inserting at head
new_node.next = head
head = new_node
return head
current = head
for i in range(position - 2): # Traverse to the (position-1)th
node
if current is None:
return None # Invalid position
current = current.next
new_node.next = current.next # Adjust pointers
current.next = new_node
return head

2. Deletion from a Singly Linked List

At the beginning:

The head is updated to point to the second node, and the first node is deleted.

Algorithm:

def delete_at_beginning(head):
if head is None:
return None # List is empty
head = head.next
return head # Return new head

At the end:

Traverse the list until the second-last node is found.

Set its next pointer to null and delete the last node.
Algorithm:

def delete_at_end(head):
if head is None:
return None # List is empty
if head.next is None:
return None # Only one element
current = head
while current.next.next is not None: # Traverse to second-last
node
current = current.next
current.next = None # Remove last node
return head

At a given position:

Traverse to the node just before the node to be deleted, and adjust pointers accordingly.

Algorithm:

def delete_at_position(head, position):

if head is None:
return None
if position == 1:
return head.next # Delete head node
current = head
for i in range(position - 2): # Traverse to (position-1)th node
if current is None:
return None # Invalid position
current = current.next
current.next = current.next.next # Adjust pointers return head

3. Traversal of a Singly Linked List

Start from the head and visit each node sequentially.

Algorithm:

def traverse(head):
current = head
while current is not None:
print(current.data)
 current = current.next

2. Doubly Linked List (DLL)

A Doubly Linked List (DLL) is a type of linked list where each node contains:

Data part: Stores the data.

Pointer to the next node: A reference to the next node in the list.

Pointer to the previous node: A reference to the previous node, allowing bi-directional traversal.

Structure of a Doubly Linked List Node:

struct Node {
int data;
struct Node* prev; // Pointer to the previous node
struct Node* next; // Pointer to the next node
};

Operations on a Doubly Linked List:

1. Insertion into a Doubly Linked List

At the beginning:

Create a new node.

Adjust the next pointer of the new node to point to the current head.

Adjust the prev pointer of the current head to point to the new node.

Update the head to the new node.

Algorithm:

def insert_at_beginning(head, data):

new_node = Node(data) # Create new node
new_node.next = head # Point new node's next to
current head
if head is not None:
head.prev = new_node # Point head's prev to new node
 head = new_node # Update head to new node
return head

At the end:

Traverse to the last node.

Adjust pointers of the last node and the new node accordingly.

Algorithm:

def insert_at_end(head, data):

new_node = Node(data)
if head is None:
head = new_node
return head
last = head
while last.next is not None:
last = last.next
last.next = new_node
new_node.prev = last
return head

At a given position:

Similar to the singly linked list, but adjust both the next and prev pointers of adjacent nodes.

Algorithm:

def insert_at_position(head, position, data):

new_node = Node(data)
if position == 1:
return insert_at_beginning(head, data)
current = head
for i in range(position - 2):
if current is None:
return None # Invalid position
current = current.next
new_node.next = current.next
if current.next is not None:
current.next.prev = new_node
current.next = new_node
new_node.prev = current
return head
2. Deletion from a Doubly Linked List

At the beginning:

Update the head to point to the second node.

Adjust the prev pointer of the new head.

Algorithm:

def delete_at_beginning(head):
if head is None:
return None
head = head.next
if head is not None:
head.prev = None
return head

At the end:

Traverse to the last node and adjust pointers accordingly.

Algorithm:

def delete_at_end(head):
if head is None:
return None
if head.next is None:
return None # Only one element
last = head
while last.next is not None:
last = last.next
last.prev.next = None
return head

At a given position:

Adjust both next and prev pointers of adjacent nodes to bypass the node being deleted.

Algorithm:

def delete_at_position(head, position):

 if head is None:
return None
if position == 1:
return delete_at_beginning(head)
current = head
for i in range(position - 2):
if current is None:
return None # Invalid position
current = current.next
current.next = current.next.next
if current.next is not None:
current.next.prev = current
return head

3. Traversal of a Doubly Linked List

Forward traversal is similar to a singly linked list.

For backward traversal, start from the last node and move through the prev pointers.

Algorithm:

def traverse_forward(head):
current = head
while current is not None:
print(current.data)
current = current.next

def traverse_backward(head):
current = head
while current.next is not None:

Circular Linked List

A circular linked list is a variation of a linked list where the last node points back to the head
node instead of pointing to NULL. This forms a circular structure, allowing traversal from any
node to any other node in the list.

Structure of a Circular Linked List

Each node in a circular linked list consists of two parts:

1. Data: Holds the value or information.

2. Next: Points to the next node in the list.

For a singly circular linked list:

The last node points to the first node (head).

For a doubly circular linked list:

Each node has a prev pointer pointing to the previous node, and the next pointer points to the
next node, forming a circular structure.

1. Circular Singly Linked List:

In Circular Singly Linked List, each node has just one pointer called the “next” pointer. The next
pointer of last node points back to the first node and this results in forming a circle. In this type
of Linked list we can only move through the list in one direction.

Representation of Circular Singly Linked List

2. Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked
list. The prev pointer points to the previous node and the next points to the next node. Here, in
addition to the last node storing the address of the first node, the first node will also store the
address of the last node.

Representation of Circular Doubly Linked List

Operations on Circular Linked List

1. Insertion
At the beginning: Insert a new node as the head, and update the last node's next to point to the
new head.
At the end: Insert a new node after the last node and update its next to point to the head.

At a specific position: Traverse to the required position and adjust the next pointers.

2. Deletion
From the beginning: Remove the head node and update the last node's next to point to the new
head.

From the end: Traverse to the second-last node and update its next to point to the head.

From a specific position: Traverse to the required position, adjust the next pointer of the
preceding node to skip the target node.

3. Traversal
Start at any node (commonly the head) and move to the next node until you reach the starting
node again.

Algorithms

Insertion at the Beginning (Singly Circular Linked List)

Algorithm: insertAtBeginning(head, data)

1. Create a new node (newNode) with the given data.
2. If head is NULL:
a. Set newNode->next = newNode.
b. Set head = newNode.
3. Else:
a. Set temp = head.
b. While temp->next != head, move temp = temp->next.
c. Set newNode->next = head.
d. Set temp->next = newNode.
e. Set head = newNode.
4. End.

Deletion from the End (Singly Circular Linked List)

Algorithm: deleteFromEnd(head)
1. If head is NULL:
a. Print "List is empty."
b. Exit.
2. Else if head->next == head:
 a. Free head.
b. Set head = NULL.
3. Else:
a. Set temp = head and prev = NULL.
b. While temp->next != head:
i. Set prev = temp.
ii. Move temp = temp->next.
c. Set prev->next = head.
d. Free temp.
4. End.

Traversal (Singly Circular Linked List)

Algorithm: traverse(head)
1. If head is NULL:
a. Print "List is empty."
b. Exit.
2. Else:
a. Set temp = head.
b. Do:
i. Print temp->data.
ii. Move temp = temp->next.
While temp != head.
3. End.

Advantages

1. Can traverse the entire list starting from any node.

2. Efficient for applications that require continuous looping through the list.

Disadvantages

1. Slightly more complex to implement than singly or doubly linked lists.

2. Traversal requires additional checks to avoid infinite loops.

Dynamic memory management

Dynamic memory management in data structures refers to the process of allocating and
deallocating memory at runtime. Unlike static memory allocation, where the memory size is fixed
at compile time, dynamic memory allows programs to request memory as needed during
execution. This is essential when the size of the data structure isn't known beforehand, making
it flexible and efficient for certain applications.

Key Concepts in Dynamic Memory Management:

1. Memory Allocation Functions:

In C/C++, the standard functions for dynamic memory management are:

malloc(size_t size) – Allocates a block of memory of specified size (in bytes) but does not
initialize it.

calloc(size_t n, size_t size) – Allocates memory for an array of n elements of size bytes each,
and initializes all bytes to zero.

realloc(void *ptr, size_t size) – Changes the size of the previously allocated memory block,
pointed to by ptr, to the new size.

free(void *ptr) – Deallocates the memory previously allocated using malloc, calloc, or realloc.

2. Heap Memory:

Dynamic memory is allocated from the heap, a large pool of memory reserved for this purpose.
Unlike the stack (used for static memory), the heap allows memory to be allocated and
deallocated in arbitrary order.

3. Data Structures that Use Dynamic Memory:

Many advanced data structures like linked lists, trees, and graphs require dynamic memory
allocation since their size can grow or shrink at runtime.

Linked List: Each node of a linked list is dynamically allocated as the list grows.

Binary Trees: Nodes are dynamically created when inserting new elements.

Hash Tables with Chaining: Each bucket in the hash table can grow dynamically as more
elements are inserted, with nodes dynamically allocated.

4. Fragmentation:

As memory is dynamically allocated and deallocated, fragmentation can occur, where free
memory is divided into small, non-contiguous blocks, making it harder to allocate large chunks
of memory.
5. Memory Leaks:

A memory leak occurs when memory is dynamically allocated but not deallocated (using free).
Over time, this can exhaust available memory, leading to performance degradation or crashes.

6. Garbage Collection:

Some languages, such as Java, Python, and C#, manage dynamic memory using automatic
garbage collection, which periodically reclaims memory that is no longer in use, preventing
memory leaks.

7. Advantages of Dynamic Memory Allocation:

Flexibility: Memory can be allocated as needed, avoiding wastage of memory.

Efficient Use of Space: Only the required amount of memory is allocated at runtime.

8. Disadvantages:

Complexity: Manual memory management (especially in languages like C/C++) introduces

complexity, with potential for memory leaks and segmentation faults.

Overhead: Dynamic memory allocation can introduce overhead compared to static memory
allocation, as it involves interaction with the system's memory management subsystem.

Dynamic memory management is crucial for implementing flexible and efficient data structures,
but it must be used with care to avoid common pitfalls such as fragmentation and memory leaks.

Garbage collection

Garbage collection in data structures refers to the process of automatically reclaiming memory
that is no longer in use by a program. In languages with automatic garbage collection (such as
Java, Python, and C#), the memory management system takes care of identifying and freeing
up memory that is no longer accessible, preventing memory leaks and ensuring efficient
memory utilization.

Key Concepts in Garbage Collection:

1. Garbage:
Garbage is memory that has been allocated but is no longer reachable by the program. For
example, if a data structure like a tree or list has nodes that are no longer referenced by any
variable, those nodes become "garbage."

2. Root Set:

The garbage collector identifies live (accessible) objects starting from a set of references called
the root set. The root set typically includes global variables, local variables in active stack
frames, and CPU registers. Any object not reachable from the root set is considered garbage
and can be reclaimed.

3. Techniques for Garbage Collection:

Reference Counting:

Each object maintains a count of how many references point to it. When this count drops to
zero, the object is garbage and can be deallocated.

Advantages: Simple to implement.

Disadvantages: Cannot handle cyclic references (e.g., two objects referencing each other with
no external references, leading to memory leaks).

Mark-and-Sweep:

The garbage collector "marks" all objects that are reachable from the root set and "sweeps"
away all unmarked objects, reclaiming their memory.

Advantages: Can handle cyclic references and is relatively simple.

Disadvantages: The program is paused during the mark-and-sweep process, which can cause
performance issues in large systems.

Generational Garbage Collection:

Objects are divided into generations based on their lifetime. Newly created objects are placed in
a young generation, and older objects that survive several rounds of collection are moved to an
older generation.

Advantages: Efficient, as most objects are short-lived and can be quickly collected, reducing the
overhead of scanning the entire heap.
Disadvantages: The overhead increases if there are many long-lived objects.

Copying Collection:

The memory is divided into two regions: an active region and a free region. The garbage
collector copies all live objects from the active region to the free region, compacting them in the
process. Once done, the free region becomes the new active region.

Advantages: Helps reduce fragmentation by compacting memory.

Disadvantages: Requires additional memory space and may have higher overhead for large
objects.

4. Data Structures and Garbage Collection:

Garbage collection is important for dynamic data structures like linked lists, trees, and graphs,
where memory is frequently allocated and deallocated during runtime. Without garbage
collection, managing memory for these structures would require manual deallocation, which can
lead to memory leaks if forgotten.

For example, in a binary tree, when a node is deleted, the garbage collector can automatically
free the memory for the node and its associated children if they are no longer referenced
elsewhere.

5. Advantages of Garbage Collection:

Simplified Memory Management: Developers don’t have to manually track memory allocation
and deallocation, reducing the risk of memory leaks.

Safety: It helps prevent common issues like dangling pointers (pointers referring to freed
memory) and double-free errors (freeing memory that’s already been deallocated).

Better Productivity: Developers can focus on logic rather than memory management.

6. Disadvantages:

Overhead: Garbage collection can introduce runtime overhead, especially if large memory
scans are needed.

Pause Times: In some algorithms (like mark-and-sweep), the system may experience pauses
while the garbage collector reclaims memory. This can affect the performance of real-time
systems.
Less Control: Unlike manual memory management (e.g., using free() in C/C++), developers
have less control over when memory is deallocated, which can lead to less efficient memory
usage in some cases.

Garbage Collection in Common Languages:

Java: Uses a generational garbage collector that combines mark-and-sweep with generational
techniques.

Python: Uses reference counting along with a cyclic garbage collector to handle cyclic
references.

C#: Utilizes the .NET garbage collector, which is generational and uses mark-and-sweep,
compacting techniques.

In C, garbage collection is not built into the language like in higher-level languages such as Java
or Python. C requires manual memory management, meaning that the programmer is
responsible for allocating and freeing memory explicitly using functions like malloc(), calloc(),
and free().

Memory Allocation in C:

malloc(size_t size): Allocates a block of memory of the specified size and returns a pointer to it.
The memory is not initialized.

calloc(size_t num, size_t size): Allocates memory for an array of num elements, each of size
bytes, and initializes the memory to zero.

free(void* ptr): Frees the memory block that was previously allocated by malloc(), calloc(), or
realloc().

Common Issues:

1. Memory Leaks: If memory is allocated using malloc() or calloc() but not freed using free(), it
results in a memory leak. Over time, this can cause the program to consume excessive memory
and possibly crash.

2. Dangling Pointers: If memory is freed but the pointer to that memory is still used, it can result
in accessing invalid memory. This is called a dangling pointer.
3. Double Free: Calling free() twice on the same pointer can lead to undefined behavior, which
may crash the program.

Manual Memory Management and Garbage Collection:

Since C does not automatically manage memory, it places the responsibility on developers to
carefully track memory usage, which can lead to errors.

Garbage collection in languages like Java handles this automatically by tracking references and
freeing memory that is no longer in use. In C, some external libraries (like the
Boehm-Demers-Weiser Garbage Collector) attempt to provide garbage collection for C
programs, but these are not part of the standard language and need to be explicitly integrated
into the project.

Best Practices for Memory Management in C:

Always pair malloc()/calloc() with free() to avoid memory leaks.

Set pointers to NULL after freeing them to avoid dangling pointer issues.

Use tools like Valgrind to detect memory leaks and other memory-related issues during
development.

By following good practices and using tools for memory debugging, developers can effectively
manage memory in C without relying on garbage collection.

In summary, garbage collection automates memory management, especially for dynamic data
structures, improving safety and productivity at the cost of some performance overhead.