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 Algorithms

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(e) 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(e) 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() method:

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

Circularly Linked List Algorithms

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

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

addFront(e) method:

• 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

addBack(e) method:

• 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

Doubly Linked List Algorithms

Note: header and trailer are the leading and trailing sentinel nodes

get(i)/set(i) methods:

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

addFront(e) method:

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

add(i,e) method:

• 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-1)'s links
• Fix node (i, now i+1)'s links
• Update size

addBack(e) method:

• 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 trailer's links
• 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]

addFront(e) method:

• 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

addBack(e) method:

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

add(i) method:

• 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:

• Remove ith element
• while( next not ull):
  • 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