Linked Lists and Its Properties

A linked list is a linear data structure as well as a dynamic data structure. A Linked list consists of nodes where each node contains a data field(to store some data values) and a reference to the next node in the list.

Properties of Linked List

  • It can be visualized as a chain of nodes where each node contains the location of the next node. You can see this in the diagram given below:
  • The structure of the node is

class Node{
    int val // variable storing the data of each node
    Node next // variable storing the address of the next blog
}
  • The first node of the linked list is called the head of the linked list. Through head, we can perform different operations on the linked list. In every linked list question, we will be given the reference of the head node of the linked list.
  • The last node of the linked list is pointing to NULL(None) which indicates that it is the last node.
  • Unlike arrays, linked list elements are not stored at contiguous memory locations.
  • Linked Lists addresses some of the limitations of arrays of having a fixed size because Linked Lists are dynamic in nature.

Advantages and Disadvantage of Linked list

PROS
  • They are dynamic in nature which allocates the memory when required.
  • Insertion and deletion operations can be easily implemented.
CONS
  • The memory is wasted as pointers require extra memory for storage.
  • No element can be accessed randomly, it has to access each node sequentially i.e. proper traversal must be done.
  • Reverse Traversing is difficult in the linked list(though we can achieve this with the help of Doubly Linked List).

Applications of Linked Lists

  • Linked lists are used to implement stacks, queues, graphs, etc.
  • Any application which has to deal with an unknown number of objects will need to use a linked list.

Critical Concepts to explore in Linked List

Suggested Problems to solve in Linked List

Happy coding! Enjoy Algorithms.