A Linked List is a data structure which can change during the execution it consists of a set of nodes linked together each node is divided into two parts one part consists of the data to be stored and the other part stores the address of the next node.
Some key points for a linked list -
Successive elements are connected by pointers.
last elements point to NULL in case of singly linked list and doubly linked list
It can grow or shrink in size during the execution of the program.
It does not waste memory space.
Types of Linked Lists -
Basic operations of Linked Lists -
Implementation of a Linked List -
Singly Linked List
class Node {
public:
int data;
Node *next;
Node()
{
data = 0;
next = NULL;
}
Node(int x)
{
this->data = x;
this->next = NULL;
}
}
class ll {
Node *head;
public:
ll(){head = NULL}
Node *insert(int pos, int x) {
Node *temp = new node(x);
Node *curr;
curr = head;
if (pos == 1)
{
temp->next = head;
head = temp;
return head;
}
for (int i = 1; i <= pos - 2 && curr != NULL; i++)
{
curr = curr->next;
}
temp->next = curr->next;
curr->next = temp;
return head;
}
Node *del(int pos) {
Node *curr;
curr = head;
if (pos == 1)
{
head = head->next;
return head;
}
for (int i = 1; i <= pos - 2 && curr != NULL; i++)
{
curr = curr->next;
}
curr->next = curr->next->next;
return head;
}
void display() {
Node *curr = head;
while (curr != NULL){
cout << curr->data << " ";
curr = curr->next;
}
}
}
Doubly Linked List -
class Node{
public:
int data;
Node *prev;
Node *next;
Node()
{
prev = NULL;
next = NULL;
data = 0;
}
Node(int x)
{
data = x;
prev = NULL;
next = NULL;
}
}
class dll{
Node *head;
public:
dll() { head = NULL }
void insertFront(int x)
{
Node *newNode = new Node(x);
NewNode->next = head;
newNode->prev = NULL;
if (head != NULL){
head->prev = newNode;
}
head = newNode;
}
void insertAfter(Node *prevNode, int x){
if (prevNode == NULL){
cout << "previous cant be null";
return;
}
Node *newNode = new Node(x);
newNode->prev = prevNode;
newNode->next = prevNode->next;
prevNode->next = newNode;
if (newNode->next != NULL){
newNode->next->prev = newNode;
}
}
void insertEnd(int x){
Node *newNode = new Node(x);
newNode->next = NULL;
Node *last = head;
if (head == NULL){
newNode->prev = NULL;
head = newNode;
return;
}
while (last->next != NULL){
last = last->next;
}
last->next = newNode;
newNode->prev = last;
}
void deleteNode(Node *delNode){
if(head == NULL || delNode == NULL){
return;
}
if(head == delNode){
head = delNode->next;
}
if(delNode->next!=NULL){
delNode->next->prev = delNode->prev;
}
if(delNode->prev!=NULL){
delNode->prev->next = delNode->next;
}
delete delNode;
}
void display(Node *node) {
Node *last;
while (node != NULL){
cout << node->data << "<==>";
last = node;
node = node->next;
}
while (last != NULL){
cout << last->data << "<==>";
last = last->prev;
}
}
}
Circular Linked List -
class Node{
public:
int data;
Node *next;
Node(){
this->data = 0;
this->next = NULL;
}
Node(int x){
this->data = x;
this->next = NULL;
}
}
class cll{
Node *head;
Node *tail;
public:
cll(){
this->head = NULL;
this->tail = NULL;
}
void insert(int x)
{
Node *newNode = newNode(x);
if (head == NULL){
head = newNode;
tail = newNode;
return;
}
tail->next = newNode;
newNode->next = head;
tail = newNode;
}
void delNode(int x)
{
Node *temp = head;
if (head == tail){
head = NULL;
tail = NULL;
return;
}
if (temp->data == x){
head = head->next;
tail->next = head;
return;
}
do{
Node *n = temp->next;
if (n->data == x){
temp->next = n->next;
break;
}
temp = temp->next;
} while (temp != head);
}
void display(){
Node *temp = head;
if (head != NULL){
do{
cout << temp->data << "-->";
if (temp->next != NULL){
temp = temp->next;
}
} while (temp != head);
}
}
}
Interview Questions on Linked Lists -
Check out all the questions about linked lists that have been asked in the FAANG interviews frequently in this GitHub repository also make sure to follow me on GitHub to stay updated on such content, also you can too contribute to this repo.
Other related blogs -
Congrats! you have learned the fundamentals of Linked List Data-Structure, make sure to subscribe to my blog to follow this series and follow me on Hashnode, where I'll be uploading content on Data Structures and Algorithms every weekend.
