A linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference or a link to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references. A drawback of linked lists is that access time is linear. Faster access, such as random access, is not feasible. Arrays have better cache locality as compared to linked lists.
Linked list types
- Singly linked list: Items can navigate in forward direction only.
- Doubly linked list: Items can navigate in both forward and backword directions.
- Circular linked list: Last node point to the first node of the list.
Linked list operations
- Insertion: Adds an element at the beginning of the list.
Deletion: Deletes an element at the beginning of the list.
Display: Displays the complete list.
Search: Searches an element using the given key.
Delete: Deletes an element using the given key.