Easy Notes Of Data structure using C unit-3 @Computer Diploma

Description

3.1 Difference between Static and Dynamic Memory Allocation

3.2 Introduction to Linked List, Terminologies

A Linked List is a linear data structure where elements are not stored at contiguous memory locations. Instead, the elements are linked using pointers.

Terminologies

• Node: The fundamental building block of a linked list. It typically contains two parts: the data and a pointer to the next node.
• Information Field / Data Field: The part of the node that stores the actual value or data.
• Next Pointer / Link Field: The part of the node that stores the address of the next node in the sequence.
• Address: The unique memory location of a node.
• Pointer: A variable that stores the address of another variable (in this case, the address of the next node). The starting point of the entire list is often referred to by a special pointer, usually called Head.
• Null Pointer: A special pointer that does not point to any memory location. In a linked list, the next pointer of the last node is always set to NULL to mark the end of the list.
• Empty List: A linked list in which the Head pointer is NULL, indicating that there are no nodes in the list.

3.3 Type of Lists

Linked lists are primarily categorized based on how the nodes are linked and traversed.

Linear Lists

A list where each node points only to the next node in a sequence, and the last node points to NULL.

1. Singly Linked List: Each node has a data field and a single pointer (next) that links to the next node. Traversal is only possible in the forward direction.
2. Doubly Linked List: Each node has a data field and two pointers:
   • next pointer: Points to the subsequent node.
   • prev pointer: Points to the preceding node. This structure allows for bidirectional traversal (both forward and backward). The prev pointer of the first node and the next pointer of the last node are NULL.

Circular List

A list where the last node links back to the first node, forming a circle. This means there is no NULL pointer at the end.

1. Circular Singly Linked List: The next pointer of the last node points back to the first node (Head).
2. Circular Doubly Linked List: The next pointer of the last node points to the first node, and the prev pointer of the first node points to the last node.

Representation of Doubly Linked List

A node structure for a doubly linked list in a language like C would look conceptually like this:

struct DoublyListNode {
    int data;                      // Information/Data field
    struct DoublyListNode* prev;   // Pointer to the previous node
    struct DoublyListNode* next;   // Pointer to the next node
};

3.4 Operations on a Singly Linked List

A singly linked list allows for a set of fundamental operations.

Creating a Linked List

The process of allocating memory for a new node (often called the Head or First node) and setting its data. For subsequent nodes, memory is allocated, data is set, and the next pointer of the previous node is updated to point to the new node.

Inserting a New Node

Insertion can be performed at three main locations:

1. At the Beginning (Head): The new node’s next pointer is set to the current Head, and the new node becomes the new Head.
2. At the End (Tail): The list is traversed to the last node, and its next pointer is updated to point to the new node. The new node’s next pointer is set to NULL.
3. In the Middle (After a specific node): The list is traversed to find the specified node, and pointers are adjusted to link the new node in the middle of the sequence.

Deleting a Node

Deletion also typically involves three cases:

1. Deleting the First Node (Head): The Head pointer is simply moved to point to the second node, and the memory of the old Head node is released.
2. Deleting the Last Node (Tail): The list must be traversed to the second-to-last node, and its next pointer is set to NULL. The memory of the last node is released.
3. Deleting a Specific Node (Middle): The list is traversed to find the node preceding the one to be deleted. The preceding node’s next pointer is updated to bypass the target node, and the target node’s memory is released.

Searching a Key in Linked List

This involves traversing the list starting from the Head and comparing the data in each node with the target key (search value). The search stops when the key is found, or when the end of the list (NULL) is reached.

Traversing a Singly Linked List

The process of visiting every node in the list exactly once. It starts from the Head node and continues by following the next pointer from one node to the next until the NULL pointer is encountered, which signifies the end of the list.

3.5 Applications of Linked List

Linked lists are a versatile data structure with numerous real-world and computer science applications.

Long Keywords on Linked List Applications

• Implementation of Abstract Data Types: Using linked lists to build other fundamental data structures, such as:
  • Stacks (Last-In, First-Out)
  • Queues (First-In, First-Out)
• Dynamic Memory Management: The operating system’s kernel often uses linked lists (specifically a free-list) to keep track of allocated and unallocated memory blocks in the heap, facilitating efficient Dynamic Memory Allocation and deallocation.
• Polynomial Manipulation: Representing and performing arithmetic operations (like addition, subtraction, and multiplication) on mathematical polynomials, where each node stores the coefficient and exponent of a term.
• Implementing Graphs: Linked lists are the core component of the Adjacency List representation of a graph, where each vertex in the graph is associated with a list of its neighboring vertices.
• Web Browser Navigation: The browser’s history and the back/forward buttons are often implemented using a Doubly Linked List to allow for easy, bidirectional movement between visited URLs.
• Music/Image/Video Playlists: Creating sequential lists in media players where songs, images, or videos are linked to their previous and next items, allowing for easy navigation.
• Undo/Redo Functionality: Most software applications implement undo/redo stacks using a Doubly Linked List to store the sequence of operations.
• Sparse Matrix Representation: Storing matrices with a very high number of zero elements (sparse matrices) efficiently by only keeping track of the non-zero elements using a specialized linked list structure.
• Operating System Scheduling: Circular Linked Lists are used in algorithms like Round-Robin Scheduling to manage and cycle through a list of processes that are waiting for the CPU.