W2295 Doubly-Linked Lists
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.
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.
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 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
|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|