singly linked list
A linked list in which each node points only to the next node, so it can be walked in one direction.
In more detail
Deleting a node requires its predecessor, because that is the node whose next pointer must change. Pushing to the front is O(1); appending is O(1) only if you also keep a tail pointer. The course's SLL class implements push-front, append, delete and find.
Related terms
- linked list — A sequence made of nodes scattered in memory, each holding a value and a pointer to the next node.
- doubly linked list — A linked list in which each node points to both the next and the previous node, so it can be walked either way and any held node removed in O(1).
- sentinel node — A dummy node that sits permanently at the start of a linked list and holds no real data, so the list is never truly empty.
Taught in
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers