Sunday, September 20, 2015

Linked List

linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference  to the next node in the sequence.

                                   

Types of Linked List: 

Based on the working of a data structure, we list only a few important linked list models.
  1. Singly Linked list
  2. Doubly Linked list 
  3. Circular Linked list

Others forms of linked lists include multiply linked list, sentinal nodes etc.

Advantages

  • Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
  • Insertion and deletion node operations are easily implemented in a linked list.
  • Linear data structures such as stacks and queues are easily executed with a linked list.
  • They can reduce access time and may expand in real time without memory overhead.

Disadvantages


  • They have a tendency to use more memory due to pointers requiring extra storage space.
  • Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
  • Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
  • Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer.