Table of Contents
Linked List
A linked list is a linear data structure in which elements are linked using pointers. It consists of nodes, where each node contains a data field and another reference (link field) to the next node in the list.
Linked List Representation in Memory
we can represent a linked list using structure and pointer (in c++, Java & Python we can use class).
// linked list
struct LList {
// data/value
int val;
// address of another node or next node
struct LList *next;
};Types of Linked Lists
There are following types of linked list
- Singly Lined-List
- Doubly Linked-List
- Circular Linked-List
Operations on Linked List
- Creation
- Insertion
- Deletion
- Traversal
- Sorting
1. Singly Linked List
A singly linked list is a type of linked list, which have one data field and one address (store address of another node)
Representation of Singly Linked List
// singly linked list
struct SLList {
// data/value
int val;
// address of another node or next node
struct LList *next;
};
Implementation of Singly Linked List
#include <iostream>
using namespace std;
// creation
struct SLList {
int data;
struct SLList *next;
SLList(int val) {
data = val;
next = NULL;
}
};
// head pointer, pointing to the first node of the linked list
struct SLList *head = NULL;
// insertion
// 1. insert new node at beginning of the linked list.
// 2. insert new node at the end of the linked list.
// 3. insert new node at the given position.
// 4. insert new node at middle position.
// insert at beginning
void insertAtBeg(int val) {
// create new node
struct SLList *newNode = new SLList(val);
if(head == NULL) {
head = newNode;
} else {
// insert node store address of head
newNode->next = head;
// head point to newly created node
head = newNode;
}
}
// 2. insert at the end of the linked list
void insertAtEnd(int val) {
struct SLList *newNode = new SLList(val);
if(head == NULL) {
head = newNode;
} else {
struct SLList *t = head;
while (t->next != NULL) {
t=t->next;
}
t->next = newNode;
}
}
// length of the linked list
int length() {
if(head == NULL) return 0;
int c=0;
struct SLList *t = head;
while (t != NULL) {
c++; t=t->next;
}
return c;
}
// 3. insert new node at the given position.
// index start with one (assume)
void insertAtPos(int val, int idx) {
if (idx > (length()+1) || idx <= 0) {
printf("Range out of length of the linked list or pos = 0 not exists\n");
} else if(idx == 1) {
// pos = 1 means insert node at first position
insertAtBeg(val);
} else {
struct SLList *t = head, *tNext = head, *newNode;
newNode = new SLList(val);
for(int i=2; i <= idx; i++) {
tNext = tNext->next;
}
for(int i=1; i<idx-1; i++) {
t = t->next;
}
t->next = newNode;
newNode->next = tNext;
}
}
// 4. insert new node at middle position.
void insertAtMid(int val) {
if (head == NULL) {
insertAtBeg(val);
} else {
struct SLList *newNode, *t = head;
newNode = new SLList(val);
int l = length();
// int mid = l%2 == 0 ? (l)/2 : (l+1)/2;
int mid = l/2;
while(mid-- > 1) {
t=t->next;
}
newNode->next = t->next;
t->next = newNode;
}
}
// deletion
// traverse linked list
void display() {
struct SLList *t = head;
while (t != NULL) {
cout << t->data << "->";
t = t->next;
}
cout << "NULL" << endl;
}
int main(int argc, char const *argv[]) {
display();
insertAtBeg(3);
insertAtBeg(2);
insertAtBeg(1);
display();
insertAtEnd(4);
insertAtEnd(5);
display();
cout << length() << endl;
insertAtMid(90);
display();
return 0;
}
// output
// NULL
// 1->2->3->NULL
// 1->2->3->4->5->NULL
// 5
// 1->2->90->3->4->5->NULL
// adding soon
// adding soon
// adding soon
2. Doubly Linked List
A doubly linked list is a type of linked list, which have one data field and two address field (the first address field store the address of the previous node, second address field store the address of the next node).
Representation of Doubly Linked List
// doubly linked list
struct DLList {
// address of prev node or next node
struct LList *prev;
// data/value
int val;
// address of another node or next node
struct LList *next;
};
3. Circular Linked List
A circular linked list is a type of linked list, the same as The doubly linked list, but the last node stores the address of the first node. this linked list forms a circle, so this linked list is called a circular linked list.
Representation of Circular Linked List
// circular linked list
struct CLList {
// address of prev node or next node
struct LList *prev;
// data/value
int val;
// address of another node or next node
struct LList *next;
};