INTRODUCTION :

  • It is a linear data structure , and the elements which are in linear are not in contiguous memory space.
  • Pointers is used to link the elements.
  • It consists of group of nodes together in a sequence.

ADVANTAGES OF LINKED LIST:

  • They are dynamic in nature (i.e) Memory is allocated when needed.
  • Insertion and deletion operations are simple in linked list because there is no need for shifting the elements after the deletion or addition.
  • And they also reduce access time.

DISADVANTAGES OF LINKED LIST :

  • Memory usage is more in linked list as it uses pointers.
  • It takes more time because of traversal.
  • Elements cannot be used randomly.

TIME COMPLEXITY :

Insertion or deletion at the beginning :    O(1)

Insertion or Deletion at the End           :    O(n)

Insertion or deletion at the middle      :    Search time+o(1)

Search                                                    :    O(n)

TYPES OF LINKED LIST :

  • Singly linked list.
  • Doubly linked list.
  • Circular linked list.

SINGLY LINKED LIST :

 It is also known as one way chain.

Singly linked list consists of TWO parts,

  • Data – ( actual representation of the linked list).
  • Link – (address of the intermediate successor).

In singly Linked List Traversal takes place in only one direction,So, it cannot traverse in the back direction.

EXAMPLE :

Let us consider an example. In the given linked list below, we have marks obtained by the student in three subjects as linked list.

In the above diagram the arrows represent the links. The last node in the list is identified as the null character. We can save as many data as we want in the list.

OPERATIONS ON SINGLY LINKED LIST :

Insertion

  • Insertion at the beginning
  • Insertion at the end
  • Insertion after a special node.

Deletion

  • Deletion at the beginning
  • Deletion at the end
  • Deletion after a special node.

Search.

Transversal.

DOUBLY LINKED LIST :

In Doubly linked list the node contains the pointer to the previous node as well as to the next node is sequence.

The previous part of the first node and last part of the next node will be empty to indicate end in each direction.

OPERATIONS ON DOUBLY LINKED LIST :

Insertion

  • Insertion at the beginning
  • Insertion at the end
  • Insertion after a special node.

Deletion

  • Deletion at the beginning
  • Deletion at the end
  • Deletion after a special node.

Search.

Transversal.

CIRCULAR LINKED LIST :

  • In circular linked list, the first element is pointed to the last and the last element is pointed to the first.
  • Both singly and doubly can be changed in Circular linked list.