An Introduction to Linked List

A Linked List is a linear data structure which consists of a group of nodes.
Unlike an array, In a linked list, elements are stored in random memory locations.

Each node contains two fields :

1. data stored at that particular address.
2. Pointer which contains the address of the next node.

The last node of the linked list contains a pointer to null to represent the termination of the linked list.
Generally, We call the first node as Head node and the last node as the Tail node in linked list.

Why linked list over array?

An array contains the following limitations:

1. The size of an array is fixed. We must know the size of the array at the time of its creation, hence it is impossible to change its size at runtime.

2. Inserting a new element in an array is expensive because we need to shift elements to create room for a new element to insert.

3. Deleting an element in an array is also expensive as it also takes the shifting of elements in an array.

Advantages of linked lists:

1. Insertion and deletion operations can be implemented very easily and these are not costly as they do not require shifting of elements.

2. They are dynamic in nature. Hence, we can change their size whenever required.

3. Stacks and queues can be implemented very easily using Linked Lists.

Disadvantages of linked lists:

1. Random access of an element is not possible in linked lists, we need to traverse linked list from starting to search an element into it.

2. It is relatively slow to process in comparision of an array.

3. Since node of a linked list conatins both data and pointer to next node, hence extra memory is required to store pointer of each node.

Types of linked lists:

There are 3 types of linked lists:

1. Singly linked list

2. Circular linked list

3. Doubly linked list

Singly linked list

Singly linked list contains a node that has both data part and pointer to the next node.
The last node of the singly linked list has a pointer to null to represent the end of the linked list.
Traversal to previous nodes is not possible in singly linked list i.e We can not traverse in the backward direction.

Circular linked list

Circular linked list is similar to singly linked list but the last node of circular linked list points to first node (head node) of linked list.

Doubly linked list

Doubly linked list contains a node that has three entries:

1. data
2. pointer to next node
3. pointer to the previous node

We can traverse in both forward and backward directions in doubly linked list.

Implementation of linked list:

I am implementing singly linked list below for the sake of understanding.

#include<iostream>
using namespace std;
/* Create a class which contains 2 properties data and pointer to next node */
class Node
{
  public:
  int data;
  Node *next;

  Node(int data)
  {
   this->data=data;
   this->next=NULL;
  }
};

/* Take Input from the user in Linked List  and Stop when a user enters data== -1 */

Node *takeInput()
{
  int data;
  cin>>data;
  /* Intially linked list is empty, hence both head and tail nodes are NULL */
  Node *head=NULL;
  Node *tail=NULL;

  while(data!=-1)
  {
    Node *newNode = new Node(data);
    /* Inserting first element in empty linked list */
    if(head==NULL)
    {
      head=newNode;
      tail=newNode;
    }
    /* List is not empty */
    else
    {
      tail->next=newNode;
      tail=tail->next;
    }
    cin>>data;
  }
  return head;
}

/* Printing elements of Linked List  1->2->3->4->5->NULL */
void printNode(Node *head)
{
  Node *temp=head;
  while(temp!=NULL)
  {
    cout<<temp->data<<" ";
    temp=temp->next;
  }
}
int main()
{
  Node *head=takeInput(); // Taking input
  printNode(head); // Printing data
}