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 new head.next to temp
• 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:

• 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	Singly Linked Lists	Doubly Linked Lists
size	O(1)	O(1)	O(1)
empty	O(1)	O(1)	O(1)
get/set	O(1)	O(n)	O(n)
add front	O(n)	O(1)	O(1)
add(i)	O(n)	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