W2295 Doubly-Linked Lists

From Coder Merlin
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder


Doubly-Linked List

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]

Singly-linked-list

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.

CautionWarnIcon.png

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.

Key Concepts[edit]

Exercises[edit]

References[edit]

CoderMerlin™ proudly recommends: