Tag: linked list

Data Structures: Doubly Linked List

A Doubly Linked List (DLL) is very similar to a Linked List, but contains an extra pointer, typically referred to as previous pointer, together with next pointer and the data.

Diagram: Doubly Linked List

Advantages over singly linked list

  • A doubly linked list can be traversed in both forward and backward direction. 
  • The delete operation for doubly linked lists is more efficient if pointer to the node to be deleted can be supplied. 
  • Quickly insert a new node before a given node. 
  • In a singly linked list, to delete a node, the pointer to the previous node is needed. To get the previous node, the list has to be traversed from the beginning. Whereas the doubly linked list can fetch the previous node using previous pointer. 

DisadvantageS 

  • Every node of the doubly linked list requires extra space for the previous pointer.
  • All operations have additional overhead because of the extra previous pointer. For example, in insertion, we need to modify previous pointers together with next pointers.

Insertion 

A node can be added in four ways:

  • At the front of the DLL 
  • After a given node. 
  • At the end of the DLL 
  • Before a given node.

Data Structures: Linked List

Like arrays, the Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

Like arrays, the Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

Diagram: Linked List

Why use a Linked List over an Array?

Arrays can be used to store linear data of similar types, but arrays have the following limitations:
1) Arrays have a fixed size – so we must know the upper limit (ceiling) on the number of elements in advance. Additionally, in most implementations, the memory allocation is equal to the upper limit regardless of usage. 
2) Inserting new elements into an array is expensive because space has to be created for the new elements and to create space, existing elements have to be shifted. 
For example, in a system, if we maintain a sorted list of IDs in an array nums[]. 
nums[] = [100, 101, 105, 200, 206]. 
And if we want to insert a new ID 104, then to maintain the sorted order, we have to move all the elements after 100 (excluding 100). 
Deletion is also expensive with arrays. For example, to delete 101 in nums[], everything after 101 has to be shifted.

Advantages over arrays:

  • Dynamic size 
  • Ease of insertion/deletion

Disadvantages:

  • Random access is disallowed. We must access elements sequentially starting from the first node and then traverse the list until we reach the element we are seeking. So an efficient binary search is not an option with linked lists in their default implementation.
  • The more segments a list is broken into the more overhead there is for locating the next linked element.
  • Extra memory space for a pointer is required with each element of the list.
  • Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not the case for linked lists.

Representation

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL. 
Each node in a list consists of at least two parts: 
1) Data 
2) Pointer (Or Reference) to the next node