Overview of Linked List

Linked list as the name suggests is a list of elements grouped linearly. 

Image Credits:Wikimedia Commons

A unit element in a linked list consists of the following components:

  1. Data
  2. Address of neighbour element/s

We refer to this unit element as a node. Therefore, a linked list is a set of nodes. The last node in the linked list points to null, indicating that the linked list has ended.


Depending upon the number of nodes that are accessed directly, linked lists are further classified into:

  1. Singly Linked List

Here, the primary node contains the address of the next node.

 Imagine playing a game of treasure hunt. You know the first clue, which contains information to direct you to the second clue and so forth.

Image Credits:Wikimedia Commons

       2.  Doubly Linked List

Here, the primary node contains the address of the previous as well as the next node.

Imagine travelling in a metro train. You know the first stop. The trains traverse back and forth according to its route.

Image Credits: Wikimedia Commons


Advantages of the Linked list:

1. Easy to insert or delete an element.

2. The size of the linked list is not fixed.

3. The dynamic nature of linked list disables wastage of memory space.


Disadvantages of the Linked list:

1. Searching and sorting are costly because we cannot access elements randomly.

2. Consumes more memory than an array to store node.


Application of linked list:

1. Implement stack, queue, hash table and graph data structure.

2. Storing polynomial numbers.

3. Operating System uses a linked list when multiple applications are running. These applications are stored in nodes.

4. Programs to play music, view images, go to next web-page.


Comments

Post a Comment

Popular posts from this blog

Overview of Tree Data Structure

Image
The tree is an abstract data structure which stores hierarchical data. For example, organisations have a hierarchical structure for employees. It is similar to the image given below. Several sergeants have to report to their respective captain. Now captains report to colonel. This colonel takes order from the general and assigns them to sergeants. Each of these consists of several levels. The general is on level 0, Colonel A and Colonel V are on level 1, Captain A, B and C are on level 2 and so on. Another terminology is height of the tree.  The height of a tree is longest path from the root node to any leaf node of the tree. Height of leaf node n=Level of leaf n+1.  Suppose we want to find the height of Private A. Height of private A= Level of Private A+1                                       =4+1                 ...
Read more

Overview of Circular Queue

Image
 Let's say another student wants to wait in the  queue to get his/her assignment checked. There is space available on the bench, but the student cannot occupy it.  If the students shift to left, then they can make space the new student. However, this is very time-consuming. So, logically the person would occupy the vacant seat. But, will make sure that when the professor calls the early entrants will go first. Assume a queue of length l. When the queue is empty, the number assigned to the front and rear is -1. In a circular queue, the front index comes right after the last index. Algorithm for enqueue: The queue is overflow if front=0 and rear=l-1. End the program. There are two cases for insertion: There is space from the rear side. If rear<l-1, then insert the element at queue[rear] and increment rear. There is space from front side.If rear=l-1 and front!=0, then set rear=0 and insert element at queue[rear]. Algorithm for dequeue: The queue is underflowing if rear=f...
Read more

Overview of Three Dimensional Array

Image
A multidimensional array is an array consisting of more than 2 dimensions.  We can perceive three dimensions at most. To visual 3-dimensional array, let's take an example of a cube. Therefore, the array is cube[3][3][3]. For better understanding, represent a 3-D array as a combination of 2-D arrays.  Note: The two-dimensional array must have the same size. To conclude, a three dimensional array has arr[sub-array number][row][column]. Application of 3-D array: To represent real-world location co-ordinates. For storing spatial data such as MRI data. 3-D modelling.
Read more