W2295 Doubly-Linked Lists

From Coder Merlin
Doubly-Linked List

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]

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 will be point to a special value called nil. If a list is empty, the head itself will point to nil.

WarnIcon.png
Caution

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

Key Concepts[edit]

Exercises[edit]

References[edit]


Designed with pride in Silicon Valley, CA, USA