Lists Study Guide
From charlesreid1
Contents
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
doublylinked 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 0indexed)
 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 0indexed)
 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 (i1), set next pointer to node (i)
 Fix node (i1)'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 setnext 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 setnext
 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
BigO 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) 
Operation Timing
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
Flags
Linked List Part of Computer Science Notes
Series on Data Structures Java: Linked Lists/Java · Linked Lists/Java/Single · Linked Lists/Java/Double · Linked Lists/Java/Circular Performance: Linked Lists/Java/Timing · Linked Lists/Java/Reverse Python: Linked Lists/Python · Linked Lists/Python/Single

Arrays Part of Computer Science Notes
Series on Data Structures Python: Arrays/Python · Arrays/Python/Sizeof · Arrays/Python/AppendCost · Arrays/Python/CaesarCipher · Arrays/Python/CompactArrays · Arrays/Python/DynamicArray Java: Arrays/Java · Arrays/Java/CaesarCipher · Arrays/Java/FisherYates · Arrays/Java/PythonList · Arrays/Java/Repeatedly_Remove Categories: Category:Python Arrays
