A linked list is a linear list abstract data structure. It is composed of nodes which contain arbitrary data for the purpose of the linked list, and a reference or two to the next (or previous) nodes to it.
It is traversed by sequential access, but it does not allow random access. It allows quick addition of items, and searching and deletion of items by sequential access.
Linked list are also used as a base of other data structures such as a stack.
- Singly-linked lists are the simplest type of linked list, where each node contains a piece of data and a reference to the next node.
- In Doubly-linked lists, nodes have a reference to both the next node and the previous node. Useful for backwards traversal of the list.
- Linear linked lists are the typical type of linked list, where the list is started or terminated by a sentinel node or a null reference.
- Circular linked list are circular in nature; the list does not end. It is similar to a linear linked list except the last node refers to the first node instead of terminating the list. In the case of doubly-linked lists, the previous node reference of the first node refers to the last node.
- Sentinel or dummy nodes are nodes added at the beginning or the end of a linked list to simplify overall coding of the linked list. This is to ensure that every (non-sentinel) node points to a "next node" in the list.
Common methods done with a linked list are:
- Adding of an item
- Inserting an item at an index
- Inserting an item at the beginning
- Inserting an item at the end
- Get/set item at index
- Remove item at index
- Remove item with specific value / equal to some other item
- Item count