Concept

Definition:

• Linear data structure with dynamic memory allocation.

• Time Complexity:

  • Access -> at O(n).

  • Deletion at O(1).

  • Searching -> O(n)

  • Insertion -> O(1)

• Types:

  • Singly Linked List: Can only be iterated from beginning

  • Doubly linked list: Can be iterated from both beginning and end
    eg: https://www.geeksforgeeks.org/count-triplets-sorted-doubly-linked-list-whose-sum-equal-given-value-x/

  • Circular linked list:
    eg: https://leetcode.com/problems/design-circular-queue/

    

Common Operations:

• Delete a node

  • Delete by value is O(N)

  • Delete by address O(1):
    https://www.geeksforgeeks.org/delete-a-node-from-linked-list-without-head-pointer/

    

• Find kth node from beginning / end O(K)

  https://leetcode.com/problems/remove-nth-node-from-end-of-list/

• Find cycle in a linked list

  https://leetcode.com/problems/linked-list-cycle/

  

• Reverse

  https://leetcode.com/problems/reverse-linked-list

  

• Swap nodes

  https://leetcode.com/problems/swap-nodes-in-pairs/

• Copy linked list

  https://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/

Where a linked list is useful?

• Doubly linked list is used as a queue

• Linked list with other data structures

Linked list & Map

• https://www.geeksforgeeks.org/lru-cache-implementation/

• https://www.geeksforgeeks.org/find-first-non-repeating-character-stream-characters/

Linked list & Priority queue

https://leetcode.com/problems/merge-k-sorted-lists/

So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.

Thank you, Have a nice day !!