# 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

The most basic list ADT is as follows:

• get
• set
• remove
• size
• empty

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

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

• get
• set
• 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.

Node class:

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

• tail pointer
• size

Node class:

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

• tail pointer only
• size

Node class:

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

• size

## Array List Implementation

(No Node class)

Array List class:

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

# Algorithms for Operations

get(i) method:

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

set(i,e) method:

• Deal with empty list case
• Step forward i times
• Replace element at pointer node

clear() method:

• Deal with empty list case
• 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

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

• 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
• Update size

removeBack() method:

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

get(i)/set(i,e) methods:

• Deal with empty list case
• Step forward i times (i is 0-indexed)
• Set/return list element at pointer node

• Deal with empty list case
• Create new node
• Save tail next as temp
• Set tail next to new node
• Set new node next to temp
• Update size

• Deal with empty list case
• Create new node
• Save tail next as temp
• Set tail next to new node
• Set new node next to temp
• Set tail to tail next - only operation different from addFront(e) method
• Update size

removeFront() method:

• Save tail next next as temp
• Set tail next to temp
• Update size

removeBack() method:

• Iterate to pointer before tail
• Set pretail next to tail next (i.e., set new tail to current head)
• Update size

get(i)/set(i) methods:

• If index < mid, use head++
• If index > mid, use tail--

• Deal with empty list case
• Create new node
• Set new first's previous pointer to header, set next pointer to old first
• Update size

• Deal with empty case
• Create new node
• Set new node's previous pointer to node (i-1), set next pointer to node (i)
• Fix node (i, now i+1)'s links
• Update size

• Deal with empty case
• Create new node
• Set new node's previous pointer to trailer's previous pointer, set next pointer to former last node
• Fix former last node's links
• Update size

removeFront() method:

• Store header next next in temp
• Set header next to temp
• Set temp previous to header
• Update size

remove(i) method:

• Store node i previous in pre
• Store node i next in post
• Set pre next to post
• Set post prev to pre
• Update size

removeBack method:

• Store trailer previous previous in temp
• Set trailer previous to temp
• Set temp next to trailer
• Update size

Can also utilize private/protected utility methods.

## Array List Algorithms

get(i)/set(i) methods:

• A[i] = e or return A[i]

• Save first element
• Set first element to new element
• while( next element not empty ):
• Save next element
• Set next element
• Do last set-next operation to clean up
• Update size
• If at capacity, resize

• Set last element
• Update size
• If at capacity, resize

• Save ith element
• Set ith element to new element
• while( next not empty ):
• Save next element
• Set next element to old save
• Do last set-next
• Update size
• If at capacity, resize

removeFront() method:

• Set first element to null
• while( next is not null ):
• first = next
• next = null
• increment next
• Update size
• Check if resize needed

removeLast() method:

• Set last element to null
• Update size
• Check if resize needed

remove(i) method:

• Set ith element to null
• while( next not null):
• ith = next
• next = null
• ith = ith+1
• Update size
• Check if resize needed

check if resize needed method:

• if size == capacity: return true
• if size < 1/4 capacity: return true

resize() method:

• Private utility method
• See grow/shrink

grow:

• Set new array = 2x old array
• Iterate over both arrays,
• Copy from one to the other

shrink:

• Set new array = 1/2 x old array (happens when 1/4 capacity)
• Iterate over both arrays
• Copy from one to the other

# Complexity and Cost

## Big O Complexity Table

Big-O Complexity of Lists

Array Lists

size O(1) O(1) O(1)
empty O(1) O(1) O(1)
get/set O(1) O(n) O(n)
add back O(1) amortized O(1) O(1)
remove front O(n) O(1) O(1)
remove(i) O(n) O(n) O(n)
remove back O(1) amortized O(n) O(1)
first O(1) O(1) O(1)
last O(1) O(1) O(1)

# OOP Principles

• Nodes, private classes, private utility methods, protection
• ADT implemented for list type
• Generic types for node containers
• Can implement positional lists
• Use the API
• Compare nodes by extending Comparable, or by implementing a Comparator