Linked List

 


What are Linked Lists

 A linked list is a linear data structure.

 Nodes make up linked lists.

 Nodes are structures made up of data and a pointer to another node.

 Usually the pointer is called next.

Arrays Vs Linked Lists

Disadvantages of Linked Lists:

  • Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists. 
  • Extra memory space for a pointer is required for each element of the list. 
  • Arrays have a better cache locality that can make a pretty big difference in performance.
  • It takes a lot of time in traversing and changing the pointers.
  • It will be confusing when we work with pointers.

Advantages of Arrays:

  • Arrays store multiple data of similar types with the same name.
  • It allows random access to elements.
  • As the array is of fixed size and stored in contiguous memory locations there is no memory shortage or overflow.
  • It is helpful to store any type of data with a fixed size.
  • Since the elements in the array are stored at contiguous memory locations it is easy to iterate in this data structure and unit time is required to access an element if the index is known.

Disadvantages of Arrays:

  • The array is static in nature. Once the size of the array is declared then we can’t modify it.
  • Insertion and deletion operations are difficult in an array as elements are stored in contiguous memory locations and the shifting operations are costly.
  • The number of elements that have to be stored in an array should be known in advance.
  • Wastage of memory is the main problem in the array. If the array size is big the less allocation of memory leads to wastage of memory.

Types of lists: There are two basic types of linked list

Singly Linked list

Doubly linked list

Singly Linked List

 Each node has only one link part

 Each link part contains the address of the next node in the list

 Link part of the last node contains NULL value which signifies the end of the node

Traversal of items can be done in the forward direction only due to the linking of every node to its next node.

Singly Linked List

Traversal of items can be done in both forward and backward directions as every node contains an additional prev pointer that points to the previous node.

Doubly linked listBasic Operations on a list

• Creating a List

• Inserting an element in a list

• Deleting an element from a list

• Searching a list

• Reversing a list

Ex: Simple program to create singly linked list (for understanding the structure)

//Implementation of Singly Linked List

#include <iostream>

using namespace std;

int main(){

    struct node{

       int v;

       struct node* nextn;

    };

    struct node n1,n2,n3,n4,n5,n0;

    n1.v = 1;

    n3.v = 3;

    n4.v = 4;

    n1.nextn = &n3;

    n3.nextn = &n4;

    n4.nextn = NULL;

    cout << "n1.nextn = " << n1.nextn << endl;

   cout << "n3.nextn = " << n3.nextn << endl;

   cout << "n4.nextn = " << n4.nextn << endl;

   // insert a next node in between

   n2.v = 2;

   n2.nextn = n1.nextn;

   n1.nextn = &n2;

   cout << "Printing result after insertion" << endl;

   cout << "n1.nextn = " << n1.nextn << endl;

   cout << "n2.nextn = " << n2.nextn << endl;

   cout << "n3.nextn = " << n3.nextn << endl;

   cout << "n4.nextn = " << n4.nextn << endl;

   // insert a node at end as tail

   n5.v = 5;

   n5.nextn = NULL;

   n4.nextn = &n5;

   cout << "Printing result after adding tail node" << endl;

   cout << "n1.nextn = " << n1.nextn << endl;

   cout << "n2.nextn = " << n2.nextn << endl;

   cout << "n3.nextn = " << n3.nextn << endl;

   cout << "n4.nextn = " << n4.nextn << endl;

   cout << "n5.nextn = " << n5.nextn << endl;

      // insert a node at beginning as head

   n0.v = 0;

   n0.nextn = &n1;

   cout << "Printing result after adding head node" << endl;

   cout << "n0.nextn = " << n0.nextn << endl;

   cout << "n1.nextn = " << n1.nextn << endl;

   cout << "n2.nextn = " << n2.nextn << endl;

   cout << "n3.nextn = " << n3.nextn << endl;

   cout << "n4.nextn = " << n4.nextn << endl;

   cout << "n5.nextn = " << n5.nextn << endl;

   //code to delete node n2 (intermediate node)

    n1.nextn = &n3;

    //n1.nextn = n2.nextn;

    delete &n2;

    cout << "Node n2 deleted";

    // code to delete node n0 (head node)

    delete &n0;

    cout << "Head node deleted";

    //code to delete tail node (last node n5)

    n4.nextn = NULL;

    delete &n5;

    cout << "Tail node deleted";

    cout << "Printing result after deleting nodes" << endl;

   cout << "n1.nextn = " << n1.nextn << endl;

   cout << "n3.nextn = " << n3.nextn << endl;

   cout << "n4.nextn = " << n4.nextn << endl;

    return 0;

}

Ex2: Implement insert, delte and display operations on a linked list.
#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next;
};
struct Node* head = NULL;
void insertion(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); //new (Node);
   new_node->data = new_data;
   new_node->next = head;
   head = new_node;
}
void append(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   struct Node* temp;
   new_node->data = new_data;
   new_node->next = NULL;
   temp = head;
   while (temp->next!=NULL){
        temp = temp->next;
   }
   temp->next=new_node;
}
void display() {
   struct Node* ptr;
   ptr = head;
   while (ptr->next != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}
void deleteHead(){
    struct Node* ptr;
    ptr = head->next;
    delete head;
    head = ptr;
}
void deleteTail(){
    struct Node* ptr;
    struct Node* temp;
    ptr = head;
    while (ptr->next->next != NULL){
        ptr = ptr->next;
    }
    temp = ptr->next;
    delete temp;
    ptr->next = NULL;
}
void deleteVal(int i){
    struct Node* ptr;
    struct Node* temp;
    ptr = head;
    int found = 0;
    int cnt = 0;
    while (cnt <=10)
    { cnt++;cout<<"cnt = " << cnt <<" data = " << ptr->data <<endl;
            if (ptr->next->data == i) {
                    cout << "Found the data" << endl;
                    temp = ptr->next;
                    ptr->next = ptr->next->next;
                    delete temp;
                    found=1;
                    break;
            }
            else {
                    ptr = ptr->next;
                }
    }
    if (found==0)
        cout << "Data not found";
}
int main() {
   insertion(6);
   insertion(1);
   append(10);
   append(14);
   insertion(2);
   insertion(9);
   insertion(7);
   //deleteHead();
   //deleteTail();
   //deleteVal(2);
   cout<<"The linked list is: "<<endl;
   display();
   return 0;
}

Ref: https://www.softwaretestinghelp.com/linked-list/

https://prepinsta.com/cpp-program/singly-linked-list/

https://www.geeksforgeeks.org/linked-list-vs-array/