Skip to content

Latest commit

 

History

History
80 lines (55 loc) · 3.85 KB

LinkedList.md

File metadata and controls

80 lines (55 loc) · 3.85 KB
Raw

Linked Lists


What is a Linked List?

A linked list is a linear data structure where each element is a separate object.
Linked list elements are not stored at contiguous location; the elements are linked using pointers.

Each node of a list is made up of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

Linked List Image

Types of Linked Lists

  • Singly Linked List : Basic Linked list consists of a node that has 1 data and 1 pointer. The pointer points to the next node and so on. The last node points to null.

  • Circular Linked List : Similar to Singly linked list but the last node points to the first one forming a circle.

  • Doubly linked List : Each node has 1 data and 2 pointers. Usually, the left pointer points to last node and right pointer points to the next node. Circular Doubly Linked List also exist where the right pointer of last node points to first node and left pointer of first node points to last node.

Linked List Operations

  1. Traversal

  2. Insert

  • Insert at start
  • Insert at Beginning
  • Insert After an element
  • Insert Before an element
  1. Delete : (Algorithms are listed in Resources Section)
  • Delete at start
  • Delete at Beginning
  • Delete After an element
  • Delete Before an element
  1. Search for element : Similar algos as that for Arrays

Advantages of Linked Lists

  1. They are a dynamic in nature which allocates the memory when required.
  2. Insertion and deletion operations can be easily implemented.
  3. Stacks and queues can be easily executed.
  4. Linked List reduces the access time.

Disadvantages of Linked Lists

  1. The memory is wasted as pointers require extra memory for storage.
  2. No element can be accessed randomly; it has to access each node sequentially.
  3. Reverse Traversing is difficult in linked list.

Applications of Linked Lists

  • Linked lists are used to implement stacks, queues, graphs, etc.
  • Linked lists let you insert elements at the beginning and end of the list.
  • In Linked Lists we don't need to know the size in advance.

Resources

You can find the Algorithms for each Operation and Many more types of Linked Lists Here:

Popular Practice Problems