1. Linked Lists
Linked lists are linear data structures where elements (called nodes) are not stored
in contiguous memory locations. Each node contains data and a pointer (or reference)
to the next node. Unlike arrays, linked lists allow dynamic memory allocation,
meaning their size can grow or shrink during runtime.
Advantages over arrays:
Dynamic size (memory is allocated as needed).
Easy insertion and deletion at any position.
Disadvantages:
Extra memory for storing pointers.
No direct access to elements (traversal is needed).
Structure of a node:
[Data | Next]
Where Data is the actual value and Next is the pointer to the next node.
2. Singly Linked List (SLL)
A singly linked list is the simplest type of linked list where each node points only to
the next node. The last node points to NULL, indicating the end of the list.
2.1 Structure of Singly Linked List
Node: Contains two fields – data and next.
Head: Pointer to the first node.
Tail: Optional, points to the last node.
Diagram:
Head -> [Data|Next] -> [Data|Next] -> [Data|Next] -> NULL
2.2 Operations on Singly Linked List
2.2.1 Traversal
Visiting each node from head to tail.
Example Program: Traversal
, Write a program that creates a singly linked list with three nodes
containing the values 10, 20, and 30. It then traverses the list from the
head node to the last node, printing each node's data followed by an
arrow (->). Finally, it prints NULL to indicate the end of the list.
#include <iostream>
using namespace std;
// Step 1: Define the structure of a Node
struct Node {
int data; // This will hold the value of the node
Node* next; // This will point to the next node in the list
};
int main() {
// Step 2: Create three nodes dynamically
Node* first = new Node(); // First node
Node* second = new Node(); // Second node
Node* third = new Node(); // Third node
// Step 3: Assign data to each node
first->data = 10;
second->data = 20;
third->data = 30;
// Step 4: Connect the nodes to form the linked list
first->next = second; // First node points to second node
second->next = third; // Second node points to third node
third->next = NULL; // Last node points to NULL (end of list)
// Step 5: Traverse the list and print the values
Linked lists are linear data structures where elements (called nodes) are not stored
in contiguous memory locations. Each node contains data and a pointer (or reference)
to the next node. Unlike arrays, linked lists allow dynamic memory allocation,
meaning their size can grow or shrink during runtime.
Advantages over arrays:
Dynamic size (memory is allocated as needed).
Easy insertion and deletion at any position.
Disadvantages:
Extra memory for storing pointers.
No direct access to elements (traversal is needed).
Structure of a node:
[Data | Next]
Where Data is the actual value and Next is the pointer to the next node.
2. Singly Linked List (SLL)
A singly linked list is the simplest type of linked list where each node points only to
the next node. The last node points to NULL, indicating the end of the list.
2.1 Structure of Singly Linked List
Node: Contains two fields – data and next.
Head: Pointer to the first node.
Tail: Optional, points to the last node.
Diagram:
Head -> [Data|Next] -> [Data|Next] -> [Data|Next] -> NULL
2.2 Operations on Singly Linked List
2.2.1 Traversal
Visiting each node from head to tail.
Example Program: Traversal
, Write a program that creates a singly linked list with three nodes
containing the values 10, 20, and 30. It then traverses the list from the
head node to the last node, printing each node's data followed by an
arrow (->). Finally, it prints NULL to indicate the end of the list.
#include <iostream>
using namespace std;
// Step 1: Define the structure of a Node
struct Node {
int data; // This will hold the value of the node
Node* next; // This will point to the next node in the list
};
int main() {
// Step 2: Create three nodes dynamically
Node* first = new Node(); // First node
Node* second = new Node(); // Second node
Node* third = new Node(); // Third node
// Step 3: Assign data to each node
first->data = 10;
second->data = 20;
third->data = 30;
// Step 4: Connect the nodes to form the linked list
first->next = second; // First node points to second node
second->next = third; // Second node points to third node
third->next = NULL; // Last node points to NULL (end of list)
// Step 5: Traverse the list and print the values
