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;
};```

`There are following types of linked list`
1. Singly Lined-List

• Creation
• Insertion
• Deletion
• Traversal
• Sorting

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

// 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);
} else {

// head point to newly created node
}
}

// 2. insert at the end of the linked list
void insertAtEnd(int val) {
struct SLList *newNode = new SLList(val);
} else {
while (t->next != NULL) {
t=t->next;
}
t->next = newNode;
}
}

// length of the linked list
int length() {
int c=0;
while (t != NULL) {
c++; t=t->next;
}

return c;
}

// 3. insert new node at the given position.
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 {
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) {
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

void display() {
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`

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;
};```

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;
};```