Data Structure: Linked List

Summary

Data Structure NameLinked List
Tagline
Use cases
TypesSingly Linked List
Doubly Linked List

Definition

Linked list is a linear collection of data.

A linked list is a data structure, that can store any data type. Data is stored in a linear order, and we can only traverse through the list and then select some items.

Simple Linked List
Simple Linked List

Use Cases

When we have a long data list, and we don’t need random access to an element, then we should use a linked list.

NOTE

Advantages of using a Linked List over an array is-

Insertion and deletion of an element in a list is less expensive than an array.
If we insert or delete an element in an array, then we have to shift the elements from that position. Everything after the insert/delete position needs to be reindexed.
But in a list, we add and/or delete the item by just changing the pointers of a node.

But the issue with Linked List is-

Every time we want access an element either by index or we try to search some data, we have to start from the head, and traverse throught the elements until we reach our desired node.
While, in an array we can access the element by index directly.

Characteristics

Elements

A Linked List data structure has the following info-

  • Head
  • Tail
  • Length
Linked list elements
Linked list elements

Each element in a linked list is called a node. So a Linked List is just a collection of nodes.

Each node has the following info-

  • value: the value(of any kind) that we want to store. Can be a string, number, object, etc. anything supported by the implemented programming language.
  • Pointer: information of the next or previous node.
    • A singly linked list has 1 pointer for the next node reference.
    • A doubly linked list has 2 pointers-
      • 1 for the next node,
      • 1 for the previous node.

NOTES

  • Random/direct access to an element is not allowed in a list. Nodes do not have any index (like an array), so the elements can not be accessed directly using any index. We have to traverse from the first node, to go to any desired node.
  • In a singly linked list, the last element(tail) has null as the pointer of the next node, as there is no next node after that.
  • In a doubly linked list-
    • The first element(head) has null as the previous node pointer, as this is no node before that.
    • the last element(tail) has null as the next node pointer, as there is no node after that.

Types

Functionality

Linked List step by step
Push item to Linked List
Pop Linked List
Pop Linked List

Leave a Comment


The reCAPTCHA verification period has expired. Please reload the page.