Difference between revisions of "W2295 Doubly-Linked Lists"
From Coder Merlin
Jeff-strong (talk | contribs) m (Editorial review and minor corrections) |
|||
| Line 1: | Line 1: | ||
[[File:Doubly-linked-list.svg|thumb|link=|Doubly-Linked List]] | [[File:Doubly-linked-list.svg|thumb|link=|Doubly-Linked List]] | ||
== Prerequisites == | == Prerequisites == | ||
{{MerlinNoteFromEditor|Need the prereqs here, or delete the heading.}} | |||
== Introduction == | == Introduction == | ||
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 | 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 == | == Linked List == | ||
[[File:Singly-linked-list.svg|thumb|right|link=|Singly-linked-list]] | [[File:Singly-linked-list.svg|thumb|right|link=|Singly-linked-list]] | ||
A | 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. | ||
{{Caution| | {{Caution| | ||
It | 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 | == Doubly Linked List == | ||
A | 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 == | == Common Functions == | ||
Linked Lists have these common functions: | |||
* '''isEmpty()''' | {{MerlinNoteFromEditor|Review: is the "iff" correct in the first bullet, or should it be "if"?}} | ||
* '''count()''' | * '''isEmpty()''' returns true iff the list is empty | ||
* '''traverse()''' | * '''count()''' counts the nodes in the list | ||
* '''append(newNode)''' | * '''traverse()''' visits each node in the list, in order | ||
* '''insert(newNode, afterNode)''' | * '''append(newNode)''' appends a node to the end of the list | ||
* '''delete(node)''' | * '''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 == | == Linked Lists vs Arrays == | ||
| Line 35: | Line 39: | ||
| Memory Size | | Memory Size | ||
| Fixed, often too large or too small | | Fixed, often too large or too small | ||
| | | Can grow or shrink as needed | ||
|- | |- | ||
| Memory Allocation Method | | Memory Allocation Method | ||
| Must be contiguous | | Must be contiguous | ||
| | | Can be freely located and relocated | ||
|- | |- | ||
| Speed of Accessing | | Speed of Accessing Data | ||
| Nearly immediate, simple arithmetic. | | Nearly immediate, simple arithmetic. Strong locality of reference. | ||
| Requires | | Requires traversing each node until target node is reached. Poor locality of reference. | ||
|- | |- | ||
| Memory Consumption | | Memory Consumption | ||
| Minimal overhead | | Minimal overhead | ||
| | | Can have substantial overhead | ||
|} | |} | ||
{{MerlinNoteFromEditor|Need the contents for the three topics below; or delete the headings.}} | |||
== Key Concepts == | == Key Concepts == | ||
== Exercises == | == Exercises == | ||
== References == | == References == | ||
Revision as of 21:02, 13 January 2022
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder
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.
Caution
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.
