Introduction to Linked List -

• A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.
• Requires extra memory to store data and pointer(address) to the next element.

  struct Node {
      int data;
      Node* next;
  }head;
  
  // Total memory allocation = 4 bytes + next pointer size
                             = 4 bytes + 8 bytes (on 64-bit machines)
                             = 12 bytes
  

• Starting node is known as head of the list and the last node always points to the null if it’s a singly/doubly linked list.
• It is dynamic in nature which allocates the memory when required.
• No element can be accessed randomly; it has to access each node sequentially.
• Reverse Traversing is difficult in the linked list.
• The memory is wasted as pointers require extra memory for storage.
• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning, middle, and end of the list.
• In Linked Lists, we don’t need to know the size in advance.

Type of Linked List:

• Singly Linked List: Items can be traversed forward only.
• Doubly Linked List: Items can be traversed forward and backward.
• Circular Linked List: The last item contains a link of the first element as next and the first element has a link to the last element as previous.

Basic Operations:

Following are the basic operations supported by a linked list.

insertion − Adds an element at the beginning/end/middle of the list.

display − Displays the complete linked list.

search − Searches an element using the given key.

delete − Deletes an element using the given key.

Now in the next blog, I will be witting about the singly linked list with python code. Stay tuned!.

Happy Learning.