A linked list is a linear data structure where elements are stored in nodes and each node points to the next node using a pointer. Unlike arrays, linked lists do not require contiguous memory locations. Each node contains two parts: data and a pointer (or link) to the next node. The linked list provides dynamic memory allocation and is widely used in scenarios where frequent insertions and deletions are required.
There are several types of linked lists, including singly linked list, doubly linked list, and circular linked list. Each type serves specific requirements and has unique structural properties. Linked lists play a critical role in Unit 2 Notes Data Structures and are essential in solving complex programming problems in B.Tech and BCA curricula.
Structure of a Node in Singly Linked List (C-like pseudocode with diagram)
struct Node {
int data;
struct Node* next;
};Insert diagram here for basic singly linked list: Node1(data,next) -> Node2(data,next) -> NULL
In the above representation, the struct Node defines a single node containing an integer data and a pointer to the next node. The last node has its next pointer as NULL, indicating the end of the list. This is the most basic form of linked list used in foundational engineering study material.
Advantages of Linked Lists
- Dynamic size: Unlike arrays, the size of a linked list can grow or shrink at runtime.
- Efficient Insertions/Deletions: Insertions and deletions are faster than arrays, especially when done at the beginning or middle.
- Memory Utilization: As memory is allocated dynamically, it reduces memory wastage.
Disadvantages of Linked Lists
- Sequential access: Unlike arrays, linked lists do not allow direct access to elements; traversal is required.
- Extra memory: Each node requires extra memory for the pointer.
- Complex operations: Reverse traversal is not possible in singly linked lists.
Types of Linked Lists
Singly Linked List: Each node contains a data field and a pointer to the next node. Traversal is done in one direction only. Doubly Linked List: Each node has three fields: data, a pointer to the next node, and a pointer to the previous node. Allows traversal in both directions. Insert diagram here for doubly linked list with previous and next pointers Circular Linked List: The last node points back to the first node. This structure allows the entire list to be traversed from any point.
Operations on Linked Lists
Insertion
- At beginning
- At the end
- After a given node
Deletion
- From beginning
- From end
- Given a node to delete
Traversal: Visiting each node from the head to the end.
Searching: Iterating through the list to find a specific value.
Algorithm for Insertion at Beginning (Singly Linked List)
void insertAtBeginning(struct Node** head, int newData) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}Insert diagram here for insertion at beginning
Algorithm for Deletion at End (Singly Linked List)
void deleteAtEnd(struct Node** head) {
struct Node* temp = *head;
if (*head == NULL) return;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
while (temp->next->next != NULL)
temp = temp->next;
free(temp->next);
temp->next = NULL;
}Insert diagram here for deletion at end
Applications of Linked Lists
- Implementation of stacks and queues
- Dynamic memory management
- Undo functionality in editors
- Adjacency list representation in graphs
Comparison Table: Array vs Linked List
| Feature | Array | Linked List |
|---|---|---|
| Size | Fixed | Dynamic |
| Access | Random | Sequential |
| Insertion/Deletion | Costly | Efficient |
| Memory | Less overhead | More due to pointers |
Real-life Examples of Linked List Usage
- Browser history (using doubly linked list)
- Music playlists
- Image viewers with next/previous navigation
Short Answer Questions (2-3 marks)
Q1. Define a linked list. A linked list is a linear data structure consisting of nodes, where each node contains data and a pointer to the next node.
Q2. What is the difference between singly and doubly linked list? A singly linked list allows traversal in one direction, while a doubly linked list allows traversal in both forward and backward directions.
Q3. List two real-life applications of linked lists.
- Music playlist navigation. 2. Browser history tracking.
Q4. Why is memory usage higher in linked lists than arrays? Linked lists use extra memory for storing pointers along with data in each node.
Q5. What is the time complexity of searching in a linked list? The time complexity is O(n) in the worst case.
Long Answer Questions (5-10 marks)
Q1. Explain the structure and operations of a singly linked list. A singly linked list is made up of nodes where each node contains a data part and a pointer to the next node. The last node points to NULL. The operations include insertion (at beginning, end, after a node), deletion (from beginning, end, or specific node), traversal (visiting each node sequentially), and searching (locating a node with specific data). These operations are implemented using pointers and require dynamic memory allocation. They are fundamental in implementing higher-level data structures such as stacks and queues.
Q2. Compare arrays and linked lists with examples. Arrays are a collection of elements stored in contiguous memory locations. They offer random access to elements but have a fixed size and costly insertion/deletion operations. Linked lists, on the other hand, are collections of nodes that are connected through pointers. They support dynamic memory allocation and efficient insertion and deletion. For example, an array of student names has a fixed size, whereas a linked list of student names can grow dynamically as new students are added.
Q3. Explain the implementation of insertion and deletion in a linked list with examples. Insertion at the beginning involves creating a new node, pointing its next to the head node, and updating the head to this new node. Deletion from the end involves traversing to the second-last node and making its next pointer NULL. These operations require proper pointer handling to avoid memory leaks or segmentation faults. Code examples and diagrams can greatly help in understanding these implementations.
Chapter Summary
Linked list is a linear data structure composed of nodes Each node has data and a pointer to the next node Types include singly doubly and circular linked lists Linked lists support dynamic memory allocation and efficient insertions/deletions Compared to arrays linked lists offer better flexibility but higher memory usage Operations include insertion deletion traversal and searching Singly linked lists allow one-way traversal while doubly linked lists support two-way traversal Circular lists connect last node to the first Applications include memory management music playlists undo features and graphs
Model Questions / Sample Internal Exam Questions
- Define a singly linked list and write its structure in C.
- What are the advantages of using linked lists over arrays?
- Write the algorithm and code for inserting a node at the end of a singly linked list.
- Describe circular linked lists with diagrams and real-life examples.
- Compare arrays, singly, and doubly linked lists.
- Write a program to delete a node from a given position in a linked list.
- Explain the concept of traversal in a linked list and write the related algorithm.
