W2295 Doubly-Linked Lists
Prerequisites[edit]
This article can be improved by: Need the prereqs here, or delete the heading.
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 points to a special value called nil. If a list is empty, the head itself will point to nil.
It is vitally important that you always maintain a pointer to every node in your list so as not to lose the node 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) that points to the prior node.
Common Functions[edit]
Linked Lists have these common functions:
This article can be improved by: Review: is the "iff" correct in the first bullet, or should it be "if"?
- 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 can 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 | Can grow or shrink as needed |
| Memory Allocation Method | Must be contiguous | Can be freely located and relocated |
| Speed of Accessing Data | Nearly immediate, simple arithmetic. Strong locality of reference. | Requires traversing each node until target node is reached. Poor locality of reference. |
| Memory Consumption | Minimal overhead | Can have substantial overhead |
This article can be improved by: Need the contents for the three topics below; or delete the headings.
