Lists Study Guide

Definitions and Variations

Definitions

list - an ordered collection of elements, not necessarily sorted, indexed to allow random access

vector - variation on a list (mathematical version of a list)

array list - a list implemented using an array, in which each element of the list is stored at a unique index

linked list - a list in which each element points to the next element, making insertion and deletion efficient at the cost of random access

iterator - a moving reference that walks through every item in the list in order

sentinel node - a linked list node that goes at the front and acts as a buffer, easing implementation of operations

head node - first node or element in a list

tail node - last node or element in a list

doubly-linked list - linked list in which each node contains two references, one to the preceding node and one to the successor node

nested class - common construct used to implement linked list nodes

circularly linked list - linked list in which last element points to first element, useful for applications involving cyclic order

cloning - produces a potentially shallow copy of the object (some objects implement cloning as a deep copy, but not all)

array list - list implementation that uses an array (usually dynamically resized) under the hood