Linked List
Definition
A linked list is a data structure that (typically) uses dynamically allocated elements called node to implement a sequence. Each node has a value field and a link field which allows access to the next item of the list.
Figure
Doubly Linked List
Figure
Operations for Singly Linked Lists
Operations are similar for doubly linked lists. The way I like to remember these is just using these diagrams, and visualizing how the arrows move around.
init- Root points to a null pointer
insert- If inserting at the start, set the new node's next pointer to the first node, then set the current root node the the new node
- If inserting in the middle, set the new note's next pointer to the node in front, and set the next pointer of the node behind to the new node
- If inserting at the end, simply set the next pointer of the last node to the new node
remove- If removing the first element, save the address of the first node, point the root node to the next node, and then delete the saved node
- If removing from the middle, save the address of the node to be deleted, then point the next pointer of the previous node to the next node of the current node (think about detaching a node) and then delete the saved node
- If removing from the end, delete the last node and set the next pointer of the previous node to null
Figure
Sorted Linked List vs Sorted Dynamic Array
See Computer Science/Programming/Arrays.
- Exists/includes/contains
- Linked list:
- Array:
because of binary search if sorted
- Linked list:
- Insert and remove:
- Linked list:
to find, to insert
- Array:
to find, to shift all elements
- Linked list: