# 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

**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) |

## 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 ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |