-
Notifications
You must be signed in to change notification settings - Fork 0
DS: Linked Lists
Rishav Ray edited this page May 11, 2025
·
2 revisions
-
A linked-list is a data-structure consisting of nodes with values and pointers. The first node is called the head.
-
Linked-lists are good for the following purposes: when the number of elements is not known in advance, when there is a lot of accesses/inserts/deletes near the head, tail, or a node whose reference is provided, when random access is not done very often, for implementing queues, etc.
-
There are 6 types of linked-lists: singly linked-lists, doubly linked-lists, circular linked-lists, doubly-circular linked-lists, multilevel linked-lists, & skip-lists.
- Singly linked-lists are the simplest type of linked-lists; in this, all the nodes have only one pointer: 'next', which points to the next node in the list.
- Doubly linked-lists are slightly more complex than the singly ones; in this, all the nodes have also have a 'prev' pointer, which points to the previous node in the list.
- Circular linked-lists are a type of singly linked list in which the last node’s next pointer points to the head, instead of null.
- Doubly circular linked-lists are pretty self-explanatory from their name- a linked-list that is doubly and circular.
- Multilevel linked-lists are trees/matrices in the form of linked-lists. Each node has two pointers: 'next'(same level) and 'child'(one level below).
- Skip-Lists are multilevel linked-lists that allow for efficient search, insertion and deletion of elements in a sorted list.