A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
Requirements
Terminology
Head: The first node in a linked list
Tail: The last node in a linked list
Pointer: Reference to another node
Node: An object containing data and pointer(s)
Types of Linked List
.png&blockId=99ad37f5-78d4-456b-b93e-868724d15868){kind=icon}
Time Complexity of Singly vs Doubly Linked Lists
Operations | Singly Linked List | Doubly Linked List |
Search | O(n) | O(n) |
Insert at head | O(1) | O(1) |
Insert at tail | O(1) | O(1) |
Remove at head | O(1) | O(1) |
Remove at tail | O(n) | O(1) |
Remove in middle | O(n) | O(n) |
