W2295 Doubly-Linked Lists
Prerequisites[edit]
Introduction[edit]
A Linked Data Structure consists of a series of records, called nodes, linked to one another through a series of pointers. This arrangement contrasts with some other data structures, such as arrays, where data are found through address calculations.
Linked List[edit]
A linked list is built by creating nodes, where each node is a structure consisting of the data (or some reference to the data) and an address field pointing to the next structure. This pointer is often referred to as next. A special pointer, called head, points to the first node of the list. If a node doesn't have a subsequent node, its next pointer will be point to a special value called nil. If a list is empty, the head itself will point to nil.
It's vitally important that we always maintain a pointer to every node in our list so as not to lose it forever.
Doubly-Linked List[edit]
A doubly-linked-list is similar to a singly-linked-list but in addition to having a next pointer each node also has a second pointer, often referred to as prev (for previous) which points to the prior node.
Common Functions[edit]
Common functions on a linked list include:
- isEmpty() - returns true iff the list is empty
- count() - counts the nodes in the list
- traverse() - visits each node in the list, in order
- append(newNode) - appends a node to the end of the list
- insert(newNode, afterNode) - inserts a node immediately after the specified node; nil may be used to indicate the first node
- delete(node) - deletes the specified node
Linked Lists vs Arrays[edit]
| Category | Arrays | Linked Lists |
|---|---|---|
| Memory Allocation | When initially created | As the program executes |
| Memory Size | Fixed, often too large or too small | May grow or shrink as needed |
| Memory Allocation Method | Must be contiguous | May be freely located and relocated |
| Speed of Accessing Particular Data | Nearly immediate, simple arithmetic. Strong locality of reference. | Requires traversal of each node until target node is reached. Poor locality of reference. |
| Memory Consumption | Minimal overhead | May have substantial overhead |
