Introduction

Quick Index

Overview
Abbreviations

This chapter discusses concepts and algorithms for a linked list. Algorithms will be shown in pseudocode or human language text.

A linked list conforms (meets) the DynamicList ADT spec (blueprint)

A linked list is an alternative to a dynamic array. For some cases a linked list will be more efficient than a DynamicArray, and vice-versa.

Some strengths of a linked list relative to a dynamic array:

Insertion is efficient at both ends of the list
Removal is efficient at both ends of the list

Weaknesses of a linked list relative to a dynamic array:

Indexed access is less efficient

Abbreviations

In this chapter, the following abbreviations are used:

Term/Element	Which Means
DLNode, Node or node	All mean "doubly linked node"
Linked List	Doubly linked list
LL	Linked List
single links in diagrams	Some diagrams show forward "next" links. If not shown, backward "prev" links are implied.
next	A link from a node to the "next" node. Also called "forward link".
prev	A link from a node to the "prev" node. Also called "backward link".
link	another term for "next" or "prev"
pointer	another term for "next" or "prev"

Note: There is also a structure called a "singly linked list" but a doubly linked is generally preferred so we will focus on it.

Data Structures And Algorithms (DSA) (Chapter 401 - Linked List Logic)

Chapter 401 - Linked List Logic Introduction

Contents Intro OO Review Concepts Design Traversal Algorithms Memory

Chapter Top Search TOC