Guest Faculty Department of Software Engineering Delhi Technological University ,New Delhi Data Structures: Linked List Linked list: A linked list is a linear data structure that consists of a series of nodes connected by pointers (in C or C++) or references (in Java, Python and JavaScript). Each node contains data and a pointer/reference to the next node in the list.
Representation of a Linked list:
Linked list can be represented as the connection of nodes in which each node points to the next node of the list. The representation of the linked list is shown below – Data Structures: Linked List Types: ➢ Singly Linked List (Nodes point to the next, enabling one-way traversal) ➢ Doubly Linked List (Nodes point to both next and previous, allowing two-way traversal.) ➢ Circular Linked List (Last node points to the first, creating a loop.) ➢ Circular Doubly Linked List (Nodes point in both directions and form a circular loop.) ➢ Header Linked List (Starts with a special header node that provides metadata or pointers for managing the list)
Advantages of Linked Lists :
➢ Dynamic size & memory efficiency: Linked lists grow or shrink easily, optimizing memory use. ➢ Fast operations: Insertion and deletion are quick (O(1)) if the position is known. ➢ Versatility: Supports various types and data, offering flexibility in applications.
Disadvantages of Linked Lists:
➢ Slower Access: Higher time complexity (O(n)) for accessing elements sequentially compared to arrays. ➢ Memory Overhead: Extra memory is needed for storing pointers in each node. ➢ Pointer Complexity: Managing pointers can increase code complexity and risk issues like memory leaks. Data Structures: 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.
Applications: Implementing stacks and queues, Managing dynamic memory allocation
➢ 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.
Applications: Browser history navigation (back and forward buttons).
Data Structures: Linked List ➢ 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.
Applications: Implementing round-robin scheduling in operating systems, Managing playlists in media
players.
➢ Circular doubly linked list:
A circular doubly linked list is defined as a circular linked list in which each node has two links connecting it to the previous node and the next node.
Applications: Undo-Redo Operations, Music Player Playlist, Cache Memory Management
Data Structures: Linked List ➢ Header Linked List: A Header Linked List includes a special node at the beginning called the header node. This node doesn't store data relevant to the list but is used for easier list management, such as tracking the list's length or providing a starting point.
This is commonly used in computer graphics, scientific computing, and machine learning applications where large, sparse datasets are handled.
Types of Header Linked List:
➢ Grounded Header Linked List:
It is a list whose last node contains the NULL pointer. In the header linked list the start pointer always points to the header node. start -> next = NULL indicates that the grounded header linked list is empty. Data Structures: Linked List ➢ Circular Header Linked List: A list in which last node points back to the header node is called circular linked list. The chains do not indicate first or last nodes. In this case, external pointers provide a frame of reference because last node of a circular linked list does not contain the NULL pointer.
Applications: Efficiently representing sparse matrices in mathematical computations, Managing free
memory blocks in dynamic memory allocation schemes. Data Structures: Linked List ➢ Skip List : A Skip List is an advanced data structure that allows fast search, insertion, and deletion operations within an ordered sequence of elements.
Skip list structure:
It is built in two layers: The lowest layer and Top layer. The lowest layer of the skip list is a common sorted linked list, and The top layers of the skip list are like an "express line" where the elements are skipped.
Advantages of Skip List:
The skip list is a robust and reliable list, Easy to implement Disadvantages of Skip List: It needs a greater amount of memory than the balanced tree, Reverse search is not permitted.
Applications: Used in databases for efficient indexing, in memory allocation systems for quick block management, and in distributed networks for fast data routing and lookup. Data Structures: Linked List Simple linked list Code: Data Structures: Linked List Q: Write a python-style pseudocode for Traversing a linked list iteratively, where the pointer head has the address of the first node of the list? Data Structures: Linked List Q: Write a Python-style pseudocode for Traversing a linked list recursively, where the pointer head has the address of the first node of the list? Data Structures: Linked List Q: Write a Python-style pseudocode for searching a key in a linked list recursively, where the pointer head has the address of the first node of the list? Data Structures: Linked List Q: Write a Python-style pseudocode for inserting a node with a key at the start of a linked list? Data Structures: Linked List Q: Write a Python-style pseudocode for inserting a node with a key after a location in a linked list? Data Structures: Linked List Q: Write a Python-style pseudocode for deleting a node from the starting of a link-list? Data Structures: Linked List Q: Write a Python-style pseudocode for deleting a node after a given location from the starting of a linked list? Data Structures: Linked List Q: Write a Python-style pseudocode for reversing a linked list iteratively? Data Structures: Linked List Q: The following python function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?
solve Data Structures: Linked List ***(Questions)***
➢ What are the advantages of circular doubly linked list over a single circular linked list? Write an algorithm to convert a sorted doubly linked list to a balanced binary search tree. ➢ Write an algorithm to perform insertion sort using a linked list. ➢ Write an algorithm that takes two linked lists, sorted in increasing order and merge the two into one linked list which is in decreasing order, and return it. ➢ Write an algorithm to concatenate two singly linked lists L1 and L2. L1 and L2 are pointers to the first node of linked lists respectively. After concatenation, L1 points to the first node of the final linked list. ➢ Write an algorithm to analyze the two single linked lists L1, L2, and form a new list L3, which contains the elements that are common in both L1 and L2 lists. ➢ Write a C program to swap Kth node from the beginning with Kth node from the end in a singly linked list ➢ Write an algorithm to perform Union and Intersection on two sorted linked lists ➢ Write a C program to add a node with data “X” before a node with data “Y” in a singly linked list ➢ Explain the operations of inserting a new node at the front, middle, and rear end of a doubly linked list. ➢ Write an algorithm to print a singly linked list in reverse order ➢ Consider a singly linked list and a data element X. Write a function to find the nth element from the end of the list.
