Introduction To Linked Lists And How It Is Different From Arrays

Why linked List

It is not always possible to know the number of data elements in advance. Sometimes the number of items need to be increased or decreased depending upon the requirement. Items may need to be added, inserted or removed. Although we can perform such operations using ordinary arrays which might not be as effective as it should be in terms of performance and memory consumption.

Why arrays are costly for random operations?

For an unknown number of items, arrays are costly in terms of memory consumption and performance because,

• We have to specify the capacity which would be the maximum possible number of items. So it might lead to more number of empty memory locations which would never be used during the lifecycle of program. In other words it will reserve all or many memory locations declared as capacity even when there are no more data items need to be stored. So it will lead to unused memory consumption issues. Here is how,
  
  
  
• When we need to insert or remove a data item in the middle of an array, it does not simply add or delete the item to specific position rather it has to shift all items to other memory locations which are below that position. So here a performance issue comes into the picture every time we add or remove an item in a list or array.

What are Linked Lists?

Linked list is a another kind of special arrangement or data structure to store multiple data items in electronic memory space. Linked lists are linear data structures in which only one element can be accessed at once. Linked list data items consists of nodes. A node is nothing but a combination of actual data and points to next node which is stored somewhere in another memory location. A pointer is just an address of memory location where the next node is stored because nodes are stored in random memory locations.



Singly Linked Lists

We can think of linked lists as a network of people in which one person has some data and also has a note of another person's address of location. Here is graphical illustration to understand the idea better.



A few points that need to be mentioned are,

• Formation of linked list
  
  Here Marton has some data and also has a note of Terry's address. Further Terry has some data and has a note of Richard's address and so on. This way multiple people form the structure of linked list. Each member is located at random locations.
  
  
• Sequential Access
  
  In linked list we can access elements sequentially. For example, when we want to reach Aaliyah's location we don't know the address of Aaliyah's locations. Therefore we have to reach to the head of linked list which is Marton.
  
  Marton knows the address of Terry who would let us know about the location of Richard.
  
  After reaching Richard, we would get the address of Aaliyah's location from Richard. So this way, one by one we have to reach to Aaliyah's location after visiting the location of all people before Aaliyah.
  
  
• Insertion
  
  We can insert element in linked list at any position if we already have the node to which we want to insert an element left and right of that node. For instance, if we want Cook, a new person to come after Richard and before Aaliyah we must have the address of location of Richard or Aaliyah. We can directly reach to Richard's location. We can place Cook anywhere at random location where he finds it to be suitable. Then we can take the note of address of Cook's location and give it to Richard. Also we will take the note of Aaliyah's location from Richard and assign it to Cook.
  
  In the same way deletion of element can be performed.

Doubly Linked List

In doubly linked list every node has data and it points to the node next and previous to it. Here in an example, Terry has note of addresses of locations of both Marton's and Richard's.



Note

The above explained example is not a real world example of linked list. It is just a metaphorical situation explaining the original concept.

How Linked Lists are different from arrays

Linked lists store elements at random memory locations whereas arrays store elements in consecutive memory locations.

Linked list cannot perform random access like arrays because elements are stored at random memory locations rather than consecutive locations. So linked lists can be accessed in a sequential manner.

Insertion and deletion in linked list is easy and performance is effective whereas arrays are expensive for such operations because it will shift elements to make a room for another element.

Linked lists can take additional memory space to store the pointer to its next element.