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

ADT and Interfaces

Basic List ADT

The most basic list ADT is as follows:

• get
• set
• add
• remove
• size
• empty

More Ornate List ADT

A slightly more ornate list ADT is given by the following list:

• get
• set
• add - to front, to back
• remove - from front, from back
• size
• empty
• contains
• clear
• first
• last

Java List ADT

The Java List ADT provides a number of methods mentioned above, in addition to others:

• get
• set
• add i
• remove i
• size
• empty
• contains
• clear

Plus other utility methods:

• indexOf
• sublist
• retainAll
• fill
• copy
• disjoint
• max/min
• replaceAll
• rotate
• shuffle
• sort
• swap

Implementations

Basically, the elements required in the class definition when we implement this data structure.

Singly Linked List

Node class:

• element - data
• next - reference
• constructor(e,n)
• get/set element
• get/set next

Linked List class:

• head pointer
• tail pointer
• size

Circular Linked List

Node class:

• element - data
• next - reference
• constructor(e,n)
• get/set element
• get/set next

Circularly Linked List class:

• tail pointer only
• size

Doubly Linked List

Node class:

• element (data)
• next - reference
• previous - reference
• constructor(e,p,n)
• get/set element
• get/set next
• get/set prev

Doubly Linked List class:

• header, trailer
• size