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 Implementation

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 Implementation

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 Implementation

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

Array List Implementation

(No Node class)

Array List class:

• capacity - constant
• data - array, generic type
• size

Algorithms for Operations

Singly Linked List

get(i) method:

• Deal with empty list case
• Start with pointer node equal to head node (element 0)
• Step forward i times (i is 0-indexed)
• Return list element at pointer node

set(i,e) method:

• Deal with empty list case
• Start with pointer node equal to head node (element 0)
• Step forward i times
• Replace element at pointer node

clear() method:

• Deal with empty list case
• Set head to null
• Update size

clone() method:

• Create new list
• (Shallow) copy items one at a time
• Return new list

equals() method:

• Check sizes are equal
• If size > 0,
• Iterate through both lists, comparing each item
• Return false if any tests fail
• Return true at the end

addFront method:

• Deal with empty list case
• Save current node to temp
• Set head to new node
• Set temp to new head next
• Update size

addBack method:

• Deal with empty list case
• (Assuming there is a tail pointer - otherwise, get it)
• Set tail next to new node
• Set tail to tail next
• Update size

removeFront method:

• Deal with empty list case
• Set head to head next
• Update size

removeBack:

• Deal with empty list case
• Iterate to the pointer before tail (pretail)
• Set pretail next to null
• Set tail to pretail
• Update size