# Code Avinya

A linked list is a linear data structure in which each element is a separate object that is connected to the next element by means of a pointer. The elements in a linked list can grow or shrink in size dynamically. Linked lists are often used to implement data structures such as stacks, queues, and associative arrays.

Linked lists are made up of nodes, which are structures that contain data and a reference (or pointer) to the next node in the list. The head and tail of a list are the first and last nodes, respectively. Each node in the list is connected to the next node by its reference. In order to traverse the list, you start at the head node and follow the references to each successive node until you reach the tail node.

When insertion and deletion operations are frequent, linked lists are typically favoured over arrays because they are quicker and simpler to operate.

However, linked lists require more memory than arrays since each node requires storage space for both its data and its reference. Additionally, linked lists are not always as efficient as arrays when searching for elements.

There are four key types of linked lists:

A singly linked list is a type of data structure in which each node contains a pointer to the next node in the sequence, as well as data. This type of linked list is linear in nature, as each node is only connected to the next node in the sequence.
• Doubly linked lists: A doubly linked list is a type of data structure in which each node contains a pointer to the previous node in the sequence and the next node in the sequence, as well as data. This type of linked list is more versatile than a singly linked list, as it allows for traversal in both directions.
• Circular linked lists: A circular linked list is a type of data structure in which the last node in the sequence points back to the first node in the sequence, thus creating a loop. This type of linked list can be used for applications where an algorithm needs to traverse the entire list before stopping.
• Circular doubly linked lists: A circular two-way linked list, commonly referred to as a doubly circular linked list, is a more complex form of a linked list that has a pointer to both the next and previous node in the sequence. Similar to the distinction between a singly linked list and a circular linked list, there is no difference between a doubly linked list and a circular doubly list. The previous field of the first node of the circular doubly linked list does not contain null.

Implementing a Linked List in C++

/* defining structure of a Node.
Each node has
1. Integer variable to store the data.
2. Pointer variable, to store the address of next node.
*/
struct Node {
int data;
Node *next;

Node(int x) {
data = x;
next = NULL;
}
};

int main(){

head = new Node(3); // creating a Node with data as '3'

Node *p;
for(int i=0;i<3;i++){
p->next = new Node(i+4); // creating a new node and assigning it to p's next.
p = p->next; // p will now point to next element
}

// LL now is [3]->[4]->[5]->[6]->NULL

/* TRAVERSAL OPERATION IN LL */

// when 'p' reaches NULL, it means end of LL is reached.
int i = 1;
while(p != NULL)
{
cout<<"For node "<<i<<" data is = "<< p->data <<endl;
p = p->next; i++;
}

// Also note the size of LL is i-1
cout<<"Size of LL = "<< i-1<<endl;

/* SEARCH OPERATION IN LL */
// search for data '5'
while(p != NULL)
{
if(p->data == 5){
cout<<"node found\n";
break; // break as element is found.
}
p = p->next; i++;
}

}

Traversal: To traverse means to go through each node one at a time.

  /* TRAVERSAL OPERATION IN LL */

// when 'p' reaches NULL, it means end of LL is reached.
int i = 1;
while(p != NULL)
{
cout<<"For node "<<i<<" data is = "<< p->data <<endl;
p = p->next; i++;
}

Insertion: The addition of a node at a certain location.

  /* INSERTION OPERATION IN LL */
// Insert at 3rd location
int pos = 3, i=1;

Node* prev;
if(pos == 1)
{ p = new Node(0);
//now make this added node as head, because it is in 1st location.
}
else{
while(p != NULL)
{
if(i == pos){
// prev is 2nd Node
// p is 3rd Node
prev->next = new Node(0);
prev->next->next = p;
break; // break as node is inserted.
}
prev = p;
p = p->next; i++;
}
}

Removal: To remove a node.

  /* Removal OPERATION IN LL */
// Removal at 3rd location
int pos = 3, i=1;
Node* prev;
if(pos == 1) // i.e head node is to be removed
{
//i.e just point to the next node
}
else{
while(p != NULL)
{
if(i == pos){
// prev is 2nd Node
// p is 3rd Node
prev->next = p->next;
// i.e 2nd node will point to 4th node, there by removing 3rd node from LL
break; // break as node is removed.
}
prev = p;
p = p->next; i++;
}
}

Searching: To value-search an element or elements.

  /* SEARCH OPERATION IN LL */
// search for data '5'
while(p != NULL)
{
if(p->data == 5){
cout<<"node found\n";
break; // break as element is found.
}
p = p->next;
}

Update: To change a node’s state.

Sorting: Putting linked list nodes in a particular order.

merging: the act of joining two linked lists together.

• Ease of Insertion and Deletion: Linked lists are dynamic in nature which allows elements to be added or removed easily at any given point in the list. This is very convenient and saves time when compared to other data structures like arrays which require elements to be shifted accordingly.
• Memory Efficiency: Linked lists use much less memory as compared to other data structures like arrays. This is because linked lists only store the address or reference of the next node instead of storing the entire data of the node.
• Flexibility: Linked lists are very flexible and can be easily manipulated as needed. Elements can be inserted or removed at any position in the list with relative ease.

• Random Access is not allowed: Linked lists do not allow random access, meaning that elements cannot be accessed directly as compared to arrays. This makes it difficult to search for a particular element or node.
• Extra Memory Space Required: Linked lists require extra memory space for the address or reference of the next node. This can be a disadvantage in terms of memory efficiency.
• Time Complexity: Linked lists have a time complexity of O(n) for searching, inserting, and deleting elements as compared to arrays which have a time complexity of O(1) for these operations. This means that linked lists are slower than arrays in terms of these operations.