Overview
Data Structures
Searching
A Singly Linked List is a linear data structure in which each element (called a node) contains two parts: data and a reference (or pointer) to the next node in the sequence.
The list starts with a head node and ends with a node pointing to null, indicating the end of the list. Operations like insertion and deletion are efficient when done at the beginning, but traversal is only possible in one direction.
// Example in C (Singly Linked List Node)
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
head = malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;Start a new empty list. Creating a new list replaces the current one.
A Singly Linked List is useful in situations where data needs to be added or removed frequently from the beginning, and memory usage should be efficient.
For example, a music playlist where each song points to the next one is like a singly linked list. You can play the next song easily, and adding a song at the beginning is fast.
It is also used in implementing stacks, where elements are added or removed from one end (LIFO – Last In, First Out).
// JS Example (Singly Linked List Playlist)
class Song {
constructor(title) {
this.title = title;
this.next = null;
}
}
let song1 = new Song("Track 1");
let song2 = new Song("Track 2");
song1.next = song2;
console.log(song1.next.title); // Output: Track 2A Doubly Linked List is a type of linked list in which each node contains three parts: data, a pointer to the next node, and a pointer to the previous node.
It allows traversal in both forward and backward directions. While it uses more memory due to the extra pointer, it offers more flexibility for operations like deletion from both ends or reverse traversal.
// Example in C (Doubly Linked List Node)
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* head = NULL;
head = malloc(sizeof(struct Node));
head->data = 1;
head->prev = NULL;
head->next = NULL;Start a new empty list. Creating a new list replaces the current one.
A Doubly Linked List is helpful when you need to navigate forward and backward between elements.
A good real-life example is a web browser's history. You can move forward and backward through visited pages, just like traversing a doubly linked list.
It’s also used in applications like text editors (undo/redo operations) and music players that allow forward/backward navigation.
// JS Example (Browser History)
class Page {
constructor(url) {
this.url = url;
this.prev = null;
this.next = null;
}
}
let page1 = new Page("google.com");
let page2 = new Page("openai.com");
page1.next = page2;
page2.prev = page1;
console.log(page2.prev.url); // Output: google.com