Data Structures : Arrays and Lists

Data Structures
- Arrays
- Singly Linked Lists
- Circularly Linked Lists
- Doubly Linked Lists
Abstract Data Types
- Array Lists
- Positional Lists

Time complexity

Operation	Dynamic array	SLL/CLL	DLL
Insert first	$\Theta(n)$	$\Theta(1)$	$\Theta(1)$
Insert last	$\Theta(1)$	$\Theta(1)$	$\Theta(1)$
Insert at index $i$	$\Theta(n-i) \in O(n)$	$\Theta(i) \in O(n)$	$\Theta(i) \in O(n)$
Delete first	$\Theta(n)$	$\Theta(1)$	$\Theta(1)$
Delete last	$\Theta(1)$	$\Theta(n)$	$\Theta(1)$
Delete at index $i$	$\Theta(n-i) \in O(n)$	$\Theta(i) \in O(n)$	$\Theta(i) \in O(n)$
Access at index $i$	$\Theta(1)$	$\Theta(i) \in O(n)$	$\Theta(i) \in O(n)$
Modify at index $i$	$\Theta(1)$	$\Theta(i) \in O(n)$	$\Theta(i) \in O(n)$
Size	max contiguous memory	max available memory	max available memory

Arrays: Scoreboard

public class GameEntry {
  private String name;   // name of the person earning this score
  private int score;     // the score value

  /** Constructs a game entry with given parameters.. */
  public GameEntry(String n, int s) { name = n; score = s; }
  /** Returns the name field. */
  public String getName() { return name; }
  /** Returns the score field. */
  public int getScore() { return score; }
  /** Returns a string representation of this entry. */
  public String toString() { return "(" + name + ", " + score + ")"; }
}

/** Class for storing high scores in an array in nondecreasing order. */
public class Scoreboard {
  private int numEntries = 0;              // number of actual entries
  private GameEntry[] board;               // array of game entries

  /** Constructs an empty scoreboard with the given capacity. */
  public Scoreboard(int capacity) { board = new GameEntry[capacity]; }
  /** Attempt to add a new high score to the collection. */
  public void add(GameEntry e) {...}
  /** Remove and return the high score at index i. */
  public GameEntry remove(int i) throws IndexOutOfBoundsException {...}
  /** Returns a string representation of the high scores list. */
  public String toString() {...}

  public static void main(String[] args) {...}
}

/** Attempt to add a new score to the collection */
public void add(GameEntry e) {
	int newScore = e.getScore();
	
	// is the new entry e really a high score?
	if (numEntries < board.length || newScore > board[numEntries-1].getScore()) {
	  if (numEntries < board.length)        // no score drops from the board
	    numEntries++;                       // so overall number increases
	  // shift any lower scores rightward to make room for the new entry
	  int j = numEntries - 1;
	  while (j > 0 && board[j-1].getScore() < newScore) {
	    board[j] = board[j-1];              // shift entry from j-1 to j
	    j--;                                // and decrement j
	  }
	  board[j] = e;                         // when done, add new entry
	}
}

/** Remove and return the high score at index i. */
public GameEntry remove(int i) throws IndexOutOfBoundsException {
	if (i < 0 || i >= numEntries)
	  throw new IndexOutOfBoundsException("Invalid index: " + i);
	GameEntry temp = board[i];                 // save the object to be removed
	for (int j = i; j < numEntries - 1; j++)   // count up from i (not down)
	  board[j] = board[j+1];                   // move one cell to the left
	board[numEntries - 1] = null;              // null out the old last score
	numEntries--;
	return temp;                               // return the removed object
}

/** Returns a string representation of the high scores list. */
public String toString() {
	StringBuilder sb = new StringBuilder("[");

	for (int j = 0; j < numEntries; j++) {
	  if (j > 0) sb.append(", ");                   // separate entries by commas
	  sb.append(board[j]);
	}
	sb.append("]");
	return sb.toString();
}

public static void main(String[] args) {
	Scoreboard highscores = new Scoreboard(5);
	String[] names = {"Rob","Mike","Rose","Jill","Jack","Anna","Paul","Bob"};
	int[] scores = {750, 1105, 590, 740, 510, 660, 720, 400};
	
	for (int i = 0; i < names.length; i++) {
	  GameEntry ge = new GameEntry(names[i], scores[i]);
	  System.out.println("Adding " + ge);
	  highscores.add(ge);
	  System.out.println(" Scoreboard: " + highscores);
	}
	System.out.println("Remove score at index " + 3); highscores.remove(3);
	System.out.println(highscores);
	System.out.println("Remove score at index " + 0); highscores.remove(0);
	System.out.println(highscores);
	System.out.println("Remove score at index " + 1); highscores.remove(1);
	System.out.println(highscores);
	System.out.println("Remove score at index " + 1); highscores.remove(1);
	System.out.println(highscores);
	System.out.println("Remove score at index " + 0); highscores.remove(0);
	System.out.println(highscores);
}

Arrays: Insertion sort

public class InsertionSort {
    
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // Move elements greater than key one position ahead
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
    
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Test the insertion sort
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.println("Original array:");
        printArray(arr);
        
        insertionSort(arr);
        
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Pseudorandom numbers

Linear congruential generator:
$$X_i = \left. \begin{cases} \text{seed} & \text{if } i = 0 \\ ( a \times X_{i - 1} + b ) ~\%~ n & \text{if } i > 0 \end{cases} \right\}$$

Example:
Suppose seed $= 467, a = 17, b = 1, n = 1$ million. Then

X₀ = 467
X₁ = (17 × 467 + 1) % 10⁶ = 7940
X₂ = (17 × 7940 + 1) % 10⁶ = 134981
X₃ = (17 × 134981 + 1) % 10⁶ = 294678
X₄ = (17 × 294678 + 1) % 10⁶ = 9527
X₅ = (17 × 9527 + 1) % 10⁶ = 161960
X₆ = (17 × 161960 + 1) % 10⁶ = 753321
X₇ = (17 × 753321 + 1) % 10⁶ = 806458

Built-in methods for java.util.Random class

Method	Functionality
nextBoolean()	Returns the next pseudorandom boolean value.
nextDouble()	Returns the next pseudorandom double value in the range [0.0, 1.0].
nextInt()	Returns the next pseudorandom int.
nextInt(n)	Returns the next pseudorandom int in the range [0, n).
setSeed(s)	Sets the seed of the generator to the long s.

2-D Arrays

Definition: A 2-D array in Java is created as array of arrays.

Declaration:
int[][] data = new int[8][10];

Valid uses:
data[i][i+1] = data[i][i] + 3;
j = data.length; // j is 8
k = data[4].length; // k is 10

2-D Arrays: Tic-Tac-Toe

/** Simulation of a Tic-Tac-Toe game (does not do strategy). */
public class TicTacToe {
  public static final int X = 1, O = -1;      // players
  public static final int EMPTY = 0;          // empty cell
  private int board[][] = new int[3][3];      // game board
  private int player;                         // current player

  /** Constructor */
  public TicTacToe() { clearBoard(); }
  /** Clears the board */
  public void clearBoard() {...}
  /** Puts an X or O mark at position i,j. */
  public void putMark(int i, int j) throws IllegalArgumentException {...}
  /** Checks whether the board configuration is a win for the given player. */
  public boolean isWin(int mark) {...}
  /** Returns the winning player's code, or 0 to indicate a tie.*/
  public int winner() {...}
  /** Returns a simple character string showing the current board. */
  public String toString() {...}
  /** Test run of a simple game */
  public static void main(String[] args) {...}
}

/** Clears the board */
public void clearBoard() {
	for (int i = 0; i < 3; i++)
	  for (int j = 0; j < 3; j++)
	    board[i][j] = EMPTY;                  // every cell should be empty
	player = X;                               // the first player is 'X'
}

/** Puts an X or O mark at position i,j. */
public void putMark(int i, int j) throws IllegalArgumentException {
	if ((i < 0) || (i > 2) || (j < 0) || (j > 2))
	  throw new IllegalArgumentException("Invalid board position");
	if (board[i][j] != EMPTY)
	  throw new IllegalArgumentException("Board position occupied");
	board[i][j] = player;       // place the mark for the current player
	player = - player;          // switch players (uses fact that O = - X)
}

/** Checks whether the board configuration is a win for the given player. */
public boolean isWin(int mark) {
	return ((board[0][0] + board[0][1] + board[0][2] == mark*3)   // row 0
	     || (board[1][0] + board[1][1] + board[1][2] == mark*3)   // row 1
	     || (board[2][0] + board[2][1] + board[2][2] == mark*3)   // row 2
	     || (board[0][0] + board[1][0] + board[2][0] == mark*3)   // column 0
	     || (board[0][1] + board[1][1] + board[2][1] == mark*3)   // column 1
	     || (board[0][2] + board[1][2] + board[2][2] == mark*3)   // column 2
	     || (board[0][0] + board[1][1] + board[2][2] == mark*3)   // diagonal
	     || (board[2][0] + board[1][1] + board[0][2] == mark*3)); // rev diag
}

/** Returns the winning player's code, or 0 to indicate a tie.*/
public int winner() {
	if (isWin(X))        return(X);
	else if (isWin(O))   return(O);
	else                 return(0);
}

/** Returns a simple character string showing the current board. */
public String toString() {
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < 3; i++) {
	  for (int j = 0; j < 3; j++) {
	    switch (board[i][j]) {
	    	case X:      sb.append("X"); break;
	    	case O:      sb.append("O"); break;
	    	case EMPTY:  sb.append(" "); break;
	    }
	    if (j < 2) sb.append("|");              // column boundary
	  }
	  if (i < 2) sb.append("\n-----\n");        // row boundary
	}
	return sb.toString();
}

/** Test run of a simple game */
public static void main(String[] args) {
	TicTacToe game = new TicTacToe();
	/* X moves: */          /* O moves: */
	game.putMark(1,1);      game.putMark(0,2);
	game.putMark(2,2);      game.putMark(0,0);
	game.putMark(0,1);      game.putMark(2,1);
	game.putMark(1,2);      game.putMark(1,0);
	game.putMark(2,0);
	System.out.println(game);
	int winningPlayer = game.winner();
	String[] outcome = {"O wins", "Tie", "X wins"};  // rely on ordering
	System.out.println(outcome[1 + winningPlayer]);
}

Singly Linked Lists (SLL)

A singly linked list, an alternative of array, is a linear sequence of nodes.

//---------------- nested Node class ----------------
/** Node of a singly linked list, which stores a reference to its
    element and to the subsequent node in the list (or null if this
    is the last node). */
private static class Node {
	private E element;        // reference to the element stored at this node
	private Node next;     // reference to the subsequent node in the list

	/** Creates a node with the given element and next node. */
	public Node(E e, Node n) { element = e; next = n; }
	/** Returns the element. */
	public E getElement() { return element; }
	/** Returns the node that follows this one (or null if no such node). */
	public Node getNext() { return next; }
	/** Sets the node's next reference to point to Node n. */
	public void setNext(Node n) { next = n; }
} //----------- end of nested Node class -----------

public class SinglyLinkedList {
  private static class Node {...}

  private Node head = null;     // head node of the list
  private Node tail = null;     // last node of the list
  private int size = 0;            // number of nodes in the list

  public SinglyLinkedList() { }    // constructs an initially empty list

  // access methods 
  public int size() { return size; }
  public boolean isEmpty() { return size == 0; }
  public E first() {...}           // returns the first element
  public E last() {...}            // returns the last element

  // update methods
  public void addFirst(E e) {...}  // adds element e to the front of the list
  public void addLast(E e) {...}   // adds element e to the end of the list
  public E removeFirst() {...}     // removes and returns the first element
}

public E first() {     // returns (but does not remove) the first element
	if (isEmpty()) return null;
	return head.getElement();
}

public E last() {      // returns (but does not remove) the last element
	if (isEmpty()) return null;
	return tail.getElement();
}

public void addFirst(E e) {    // adds element e to the front of the list
	head = new Node<>(e, head);  // create and link a new node
	if (size == 0)
	  tail = head;               // special case: new node becomes tail also
	size++;
}

public void addLast(E e) {              // adds element e to the end of the list
	Node newest = new Node<>(e, null); // node will eventually be the tail
	if (isEmpty())
	  head = newest;                      // special case: previously empty list
	else
	  tail.setNext(newest);               // new node after existing tail
	tail = newest;                        // new node becomes the tail
	size++;
}

public E removeFirst() {         // removes and returns the first element
	if (isEmpty()) return null;    // nothing to remove
	E answer = head.getElement();
	head = head.getNext();         // will become null if list had only one node
	size--;
	if (size == 0)
	  tail = null;                 // special case as list is now empty
	return answer;
}

Time complexity

Operation	Time
First	$\Theta(1)$
Last	$\Theta(1)$
AddFirst	$\Theta(1)$
AddLast	$\Theta(1)$
RemoveFirst	$\Theta(1)$
RemoveLast	$\Theta(n)$

Circularly Linked Lists (CLL)

Applications requiring cyclic order:

Operating system: Round-robin scheduling of processes/jobs
Multiplayer games: Scheduling of player turns
Buses and subways: Scheduling of stops in a continuous loop

Round-robin scheduling of processes:

Round-robin scheduler can be implemented using a singly linked list L by repeatedly performing:

process $p$ = $L$.removeFirst()
Give a time slice to process $p$
$L$.addLast($p$)

Designing a CircularlyLinkedList class:
CircularlyLinkedList = SinglyLinkedList + (tail.next ← head) + rotate() method
(rotate() moves the first element to the end of the list)

Round-robin scheduler can be implemented using a circularly linked list C by repeatedly performing:

Give a time slice to process C.first()
C.rotate()

Additional optimizations:

Head reference is no longer required. Head can be accessed as tail.getNext()
Maintaining only the tail reference is simpler, time-, and space-efficient.
This implementation is superior to singly linked list implementation.

Rotate operation

Insert element at head

public class CircularlyLinkedList {
  // nested node class identical to that of the SinglyLinkedList class
  private static class Node {...}

  private Node tail = null;       // we store tail (but not head)
  private int size = 0;              // number of nodes in the list
  public CircularlyLinkedList() { }  // constructs an initially empty list

  // access methods
  public int size() { return size; }
  public boolean isEmpty() { return size == 0; }
  public E first() {...}             // returns the first element
  public E last() {...}              // returns the last element

  // update methods
  public void rotate() {...}         // rotate the first element to the last
  public void addFirst(E e) {...}    // adds element e to the front
  public void addLast(E e) {...}     // adds element e to the end
  public E removeFirst() {...}       // removes and returns the first element
}

public E first() {                       // returns the first element
	if (isEmpty()) return null;
	return tail.getNext().getElement();    // the head is after the tail
}

public E last() {                        // returns the last element
	if (isEmpty()) return null;
	return tail.getElement();
}

public void rotate() {             // rotate the first element to the last
	if (tail != null)                // if empty, do nothing
	  tail = tail.getNext();         // the old head becomes the new tail
}

public void addFirst(E e) {        // adds element e to the front of the list
	if (size == 0) {
	  tail = new Node<>(e, null);
	  tail.setNext(tail);            // link to itself circularly
	} else {
	  Node newest = new Node<>(e, tail.getNext());
	  tail.setNext(newest);
	}
	size++;
}

public void addLast(E e) {            // adds element e to the end of the list
	addFirst(e);                        // insert new element at front of list
	tail = tail.getNext();              // now new element becomes the tail
}

public E removeFirst() {              // removes and returns the first element
	if (isEmpty()) return null;         // nothing to remove
	Node head = tail.getNext();
	if (head == tail) tail = null;      // must be the only node left
	else tail.setNext(head.getNext());  // removes "head" from the list
	size--;
	return head.getElement();
}

Time complexity

Operation	Time
First	$\Theta(1)$
Last	$\Theta(1)$
AddFirst	$\Theta(1)$
AddLast	$\Theta(1)$
RemoveFirst	$\Theta(1)$
RemoveLast	$\Theta(n)$

Doubly Linked Lists (DLL)

Advantages of using sentinels:

Header and trailer nodes never change, only the nodes between them change
Insertions and deletions can be handled in a unified manner

Inserting a node

Inserting at the front

Deleting a node

Methods

Method	Functionality
size()	Returns the number of elements in the list.
isEmpty()	Returns true if the list is empty, and false otherwise.
first()	Returns the first element in the list.
last()	Returns the last element in the list.
addFirst(e)	Adds a new element to the front of the list.
addLast(e)	Adds a new element to the end of the list.
removeFirst()	Removes and returns the first element of the list.
removeLast()	Removes and returns the last element of the list.

public class DoublyLinkedList {
  // nested Node class
  private static class Node {...}
  private Node header;                    // header sentinel
  private Node trailer;                   // trailer sentinel
  private int size = 0;

  // access methods
  public DoublyLinkedList() {...}
  public int size() {...}
  public boolean isEmpty() {...}
  public E first() {...}
  public E last() {...}

  // update methods
  public void addFirst(E e) {...}
  public void addLast(E e) {...}
  public E removeFirst() {...}
  public E removeLast() {...}
  // private update methods
  private void addBetween(E e, Node predecessor, Node successor) {...}
  private E remove(Node node) {...}
}

//---------------- nested Node class ----------------
private static class Node {
	private E element;          // reference to the element stored at this node
	private Node prev;       // reference to the previous node in the list
	private Node next;       // reference to the subsequent node in the list

	public Node(E e, Node p, Node n) {
	  element = e; prev = p; next = n;
	}
	public E getElement() { return element; }
	public Node getPrev() { return prev; }
	public Node getNext() { return next; }
	public void setPrev(Node p) { prev = p; }
	public void setNext(Node n) { next = n; }
} //----------- end of nested Node class -----------

public DoublyLinkedList() {
	header = new Node<>(null, null, null);     // create header
	trailer = new Node<>(null, header, null);  // trailer is preceded by header
	header.setNext(trailer);                   // header is followed by trailer
}

// public access methods
public int size() { return size; }

public boolean isEmpty() { return size == 0; }

public E first() {
	if (isEmpty()) return null;
	return header.getNext().getElement();      // first element is beyond header
}

public E last() {
	if (isEmpty()) return null;
	return trailer.getPrev().getElement();     // last element is before trailer
}

/* Adds an element to the linked list in between the given nodes. */
private void addBetween(E e, Node predecessor, Node successor) {
	// create and link a new node
	Node newest = new Node<>(e, predecessor, successor);
	predecessor.setNext(newest);
	successor.setPrev(newest);
	size++;
}

/* Removes the given node from the list and returns its element. */
private E remove(Node node) {
	Node predecessor = node.getPrev();
	Node successor = node.getNext();
	predecessor.setNext(successor);
	successor.setPrev(predecessor);
	size--;
	return node.getElement();
}

/* Adds an element to the front of the list. */
public void addFirst(E e) {
	addBetween(e, header, header.getNext());   // place just after the header
}

/* Adds an element to the end of the list. */
public void addLast(E e) {
	addBetween(e, trailer.getPrev(), trailer); // place just before the trailer
}

/* Removes and returns the first element of the list. */
public E removeFirst() {
	if (isEmpty()) return null;                // nothing to remove
	return remove(header.getNext());           // first element is beyond header
}

/* Removes and returns the last element of the list. */
public E removeLast() {
	if (isEmpty()) return null;                // nothing to remove
	return remove(trailer.getPrev());          // last element is before trailer
}

List ADT

Method	Functionality
size()	Returns the number of elements in the list.
isEmpty()	Returns a boolean indicating whether the list is empty.
get(i)	Returns the element of the list having index i; an error condition occurs if i is not in range [0, size()-1].
set(i, e)	Replaces the element at index i with e, and returns the old element; an error occurs if i is not in range [0, size()-1].
add(i, e)	Inserts a new element e at index i, moving all subsequent elements one index later; an error occurs if i is not in range [0, size()].
remove(i)	Removes and returns the element at index i, moving all subsequent elements one index earlier; an error occurs if i is not in range [0, size()-1].

Operations on a list

Method	Return value	List contents
add(0, A)	-	(A)
add(0, B)	-	(B, A)
get(1)	A	(B, A)
set(2, C)	error	(B, A)
add(2, C)	-	(B, A, C)
add(4, D)	error	(B, A, C)
remove(1)	A	(B, C)
add(1, D)	-	(B, D, C)
add(1, E)	-	(B, E, D, C)
get(4)	error	(B, E, D, C)
add(4, F)	-	(B, E, D, C, F)
set(2, G)	D	(B, E, G, C, F)
get(2)	G	(B, E, G, C, F)

/* A simplified version of the java.util.List interface. */
public interface List {
	int size();
	boolean isEmpty();

	/* Returns (but does not remove) the element at index i. */
	E get(int i) throws IndexOutOfBoundsException;

	/* Replaces element at index i with e, and returns replaced element. */
	E set(int i, E e) throws IndexOutOfBoundsException;

	/* Inserts e to be at index i, shifting subsequent elements later. */
	void add(int i, E e) throws IndexOutOfBoundsException;

	/* Removes the element at index i, shifting subsequent elements earlier. */
	E remove(int i) throws IndexOutOfBoundsException;
}

Array Lists

Implement the List ADT using an array. Get/set methods are fast, but add/remove methods are slow.

public class ArrayList implements List {
  public static final int CAPACITY=16;     // default array capacity
  private E[] data;                        // generic array used for storage
  private int size = 0;                    // current number of elements

  public ArrayList() { this(CAPACITY); }   // constructs list with default cap.
  public ArrayList(int capacity) { data = (E[]) new Object[capacity]; }

  public int size() { return size; }
  public boolean isEmpty() { return size == 0; }
  public E get(int i) throws IndexOutOfBoundsException {...}
  public E set(int i, E e) throws IndexOutOfBoundsException {...}
  public void add(int i, E e) throws IndexOutOfBoundsException {...}
  public E remove(int i) throws IndexOutOfBoundsException {...}

  // utility methods
  /** Checks whether the given index is in the range [0, n-1]. */
  protected void checkIndex(int i, int n) throws IndexOutOfBoundsException {...}
  /** Resizes internal array to have given capacity >= size. */
  protected void resize(int capacity) {...}
}

/* Returns (but does not remove) the element at index i. */
public E get(int i) throws IndexOutOfBoundsException {
	checkIndex(i, size);
	return data[i];
}

/* Replaces the element at the specified index, and
 * returns the element previously stored. */
public E set(int i, E e) throws IndexOutOfBoundsException {
	checkIndex(i, size);
	E temp = data[i];
	data[i] = e;
	return temp;
}

/* Inserts the given element at the specified index of the list, shifting all
 * subsequent elements in the list one position further to make room. */
public void add(int i, E e) throws IndexOutOfBoundsException {
	checkIndex(i, size + 1);
	if (size == data.length)               // not enough capacity
	  resize(2 * data.length);             // so double the current capacity
	for (int k=size-1; k >= i; k--)        // start by shifting rightmost
	  data[k+1] = data[k];
	data[i] = e;                           // ready to place the new element
	size++;
}

/* Removes and returns the element at the given index, shifting all subsequent
 * elements in the list one position closer to the front. */
public E remove(int i) throws IndexOutOfBoundsException {
	checkIndex(i, size);
	E temp = data[i];
	for (int k=i; k < size-1; k++)         // shift elements to fill hole
	  data[k] = data[k+1];
	data[size-1] = null;                   // help garbage collection
	size--;
	return temp;
}

/* Checks whether the given index is in the range [0, n-1]. */
protected void checkIndex(int i, int n) throws IndexOutOfBoundsException {
	if (i < 0 || i >= n)
	  throw new IndexOutOfBoundsException("Illegal index: " + i);
}

/* Resizes internal array to have given capacity >= size. */
protected void resize(int capacity) {
	E[] temp = (E[]) new Object[capacity];     // safe cast
	for (int k=0; k < size; k++)
	  temp[k] = data[k];
	data = temp;                               // start using the new array
}

Dynamic array

Adding elements leads to the overflow problem. The overflow problem can be handled by growing the array.

Grow-Array($A, n$)

Allocate a new array $B$ with larger capacity.
Set $B[k] = A[k]$, for $k = 0, …, n-1$, where $n$ denotes current number of items.
Set $A = B$, that is, we henceforth use the new array to support the list.
Leave the old array to be garbage collected.

Amortized analysis of dynamic arrays

Amortized analysis. Show that performing a sequence of operations is quite efficient.

Core idea. Instead of considering worst-case time per operation, consider the average time taken per operation.

Use geometric progressions: $\langle a, ar, ar^2, \ldots \rangle$, such that $r \in \mathbb{R}$ and $r > 1$. Total time to perform n add operations is $\Theta(n)$. (The value r chosen depends on the trade-off between runtime efficiency and memory usage.)

Do not use arithmetic progressions: $\langle a, a + d, a + 2d, \ldots \rangle$, such that $d \in \mathbb{N}$. Total time to perform n add operations is $\Theta(n^2)$.

Shrinking the dynamic array

What if you repeatedly remove elements from an arbitrarily large array?
What if there is an oscillation between growing and shrinking the underlying array?
The array capacity is halved when the number of elements falls below 1/4th of the capacity

String vs. StringBuilder class

public String repeat1(char c, int n) {
	String answer = "";
	for (int j=0; j < n; j++)
		answer += c;
	return answer;
}

Static array. Resize every time. Time for $n$ adds is $\Theta(n^2)$.

public String repeat2(char c, int n) {
	StringBuilder sb = new StringBuilder();
	for (int j=0; j < n; j++)
		sb.append(c);
	return sb.toString();
}

Dynamic array. Resize a few times. Time for $n$ adds is $\Theta(n)$.

Positional Lists

Position in a queue = node reference

Cursor in a text editor = node reference

Position or cursor

Method	Functionality
getElement()	Returns the element stored at this position.

The position of an element does not change even when its index changes due to insertions/deletions in the list.

Position cursor = guests.first();
while (cursor != null) {
	System.out.println(cursor.getElement());
	cursor = guests.after(cursor);    // advance to the next position (if any)
}

Access and update methods

Method	Functionality
first()	Returns the position of the first element of L (or null if empty).
last()	Returns the position of the last element of L (or null if empty).
before(p)	Returns the position of L immediately before position p (or null if p is the first position).
after(p)	Returns the position of L immediately after position p (or null if p is the last position).
isEmpty()	Returns true if list L does not contain any elements.
size()	Returns the number of elements in list L.

Method	Functionality
addFirst(e)	Inserts a new element e at the front of the list, returning the position of the new element.
addLast(e)	Inserts a new element e at the back of the list, returning the position of the new element.
addBefore(p,e)	Inserts a new element e just before position p, returning the position of the new element.
addAfter(p,e)	Inserts a new element e just after position p, returning the position of the new element.
set(p,e)	Replaces the element at position p with element e, returning the element formerly at position p.
remove(p)	Removes and returns the element at position p, invalidating the position.

Operations

Method	Return value	List contents
addLast(8)	p	(8_p)
first()	p	(8_p)
addAfter(p, 5)	q	(8_p, 5_q)
before(q)	p	(8_p, 5_q)
addBefore(q, 3)	r	(8_p, 3_r, 5_q)
getElement()	3	(8_p, 3_r, 5_q)
after(p)	r	(8_p, 3_r, 5_q)
before(p)	null	(8_p, 3_r, 5_q)
addFirst(9)	s	(9_s, 8_p, 3_r, 5_q)
remove(last())	5	(9_s, 8_p, 3_r)
set(p, 7)	8	(9_s, 7_p, 3_r)
remove(q)	error	(9_s, 7_p, 3_r)

public interface Position {
  E getElement() throws IllegalStateException;
}

public interface PositionalList {
  int size();
  boolean isEmpty();
  Position first();
  Position last();
  Position before(Position p) throws IllegalArgumentException;
  Position after(Position p) throws IllegalArgumentException;
  Position addFirst(E e);
  Position addLast(E e);
  Position addBefore(Position p, E e) throws IllegalArgumentException;
  Position addAfter(Position p, E e) throws IllegalArgumentException;
  E set(Position p, E e) throws IllegalArgumentException;
  E remove(Position p) throws IllegalArgumentException;
}

public class LinkedPositionalList implements PositionalList {
	private static class Node implements Position {...}
	private Node header;             // header sentinel
	private Node trailer;            // trailer sentinel
	private int size = 0;

	public LinkedPositionalList() {...}
	private Node validate(Position p) throws IllegalArgExcep {...}
	private Position position(Node node) {...}
	public int size() {...}
	public boolean isEmpty() {...}
	public Position first() {...}
	public Position last() {...}
	public Position before(Position p) throws IllegalArgExcep {...}
	public Position after(Position p) throws IllegalArgExcep {...}
	private Position addBetween(E e, Node pred, Node succ) {...}
	public Position addFirst(E e) {...}
	public Position addLast(E e) {...}
	public Position addBefore(Position p, E e) throws IllegalArgExcep {...}
	public Position addAfter(Position p, E e) throws IllegalArgExcep {...}
	public E set(Position p, E e) throws IllegalArgExcep {...}
	public E remove(Position p) throws IllegalArgExcep {...}
}

//---------------- nested Node class ----------------
private static class Node implements Position {
	private E element;        // reference to the element stored at this node
	private Node prev;     // reference to the previous node in the list
	private Node next;     // reference to the subsequent node in the list
	public Node(E e, Node p, Node n)
	{ element = e; prev = p; next = n; }

	// public accessor methods
	public E getElement() throws IllegalStateException {
	  if (next == null)       // convention for defunct node
	    throw new IllegalStateException("Position no longer valid");
	  return element;
	}
	public Node getPrev() { return prev; }
	public Node getNext() { return next; }
	public void setElement(E e) { element = e; }
	public void setPrev(Node p) { prev = p; }
	public void setNext(Node n) { next = n; }
} //----------- end of nested Node class -----------

public LinkedPositionalList() {
	header = new Node<>(null, null, null);      // create header
	trailer = new Node<>(null, header, null);   // trailer is preceded by header
	header.setNext(trailer);                    // header is followed by trailer
}

private Node validate(Position p) throws IllegalArgumentException {
	if (!(p instanceof Node)) throw new IllegalArgumentException("Invalid p");
	Node node = (Node) p;     // safe cast
	if (node.getNext() == null)     // convention for defunct node
		throw new IllegalArgumentException("p is no longer in the list");
	return node;
}

private Position position(Node node) {
	if (node == header || node == trailer)
		return null;   // do not expose user to the sentinels
	return node;
}

public Position first() { return position(header.getNext()); }

public Position last() { return position(trailer.getPrev()); }

public Position before(Position p) throws IllegalArgumentException {
	Node node = validate(p);
	return position(node.getPrev());
}

public Position after(Position p) throws IllegalArgumentException {
	Node node = validate(p);
	return position(node.getNext());
}

private Position addBetween(E e, Node pred, Node succ) {
	Node newest = new Node<>(e, pred, succ);  // create and link a new node
	pred.setNext(newest); succ.setPrev(newest); size++;
	return newest;
}

public Position addFirst(E e)
{ return addBetween(e, header, header.getNext()); }

public Position addLast(E e)
{ return addBetween(e, trailer.getPrev(), trailer); }

public Position addBefore(Position p, E e)
                                throws IllegalArgumentException {
	Node node = validate(p);
	return addBetween(e, node.getPrev(), node);
}

public Position addAfter(Position p, E e)
                            throws IllegalArgumentException {
	Node node = validate(p);
	return addBetween(e, node, node.getNext());
}

public E set(Position p, E e) throws IllegalArgumentException {
	Node node = validate(p);
	E answer = node.getElement();
	node.setElement(e);
	return answer;
}

public E remove(Position p) throws IllegalArgumentException {
	Node node = validate(p);
	Node predecessor = node.getPrev();
	Node successor = node.getNext();
	predecessor.setNext(successor);
	successor.setPrev(predecessor);
	size--;
	E answer = node.getElement();
	node.setElement(null);           // help with garbage collection
	node.setNext(null);              // and convention for defunct node
	node.setPrev(null);
	return answer;
}

Method	Time $T(n)$
size()	$\Theta(1)$
isEmpty()	$\Theta(1)$
first(), last()	$\Theta(1)$
before($p$), after($p$)	$\Theta(1)$
addFirst($e$), addLast($e$)	$\Theta(1)$
addBefore($p$, $e$), addAfter($p$, $e$)	$\Theta(1)$
set($p$, $e$)	$\Theta(1)$
remove($p$)	$\Theta(1)$

Insertion sort

/** Insertion-sort of a positional list of integers into nondecreasing order */
public static void insertionSort(PositionalList list) {
	Position marker = list.first(); // last position known to be sorted
	while (marker != list.last()) {
		Position pivot = list.after(marker);
		int value = pivot.getElement(); // number to be placed
		if (value > marker.getElement()) // pivot is already sorted
			marker = pivot;
		else { // must relocate pivot
			Position walk = marker; // find leftmost item greater than value
			while (walk != list.first() && list.before(walk).getElement() > value)
				walk = list.before(walk);
			list.remove(pivot); // remove pivot entry and
			list.addBefore(walk, value); // reinsert value in front of walk
		}
	}
}

Data Structures : Arrays and Lists

Contents

Time complexity

Arrays: Scoreboard

Arrays: Insertion sort

Pseudorandom numbers

Built-in methods for java.util.Random class

2-D Arrays

2-D Arrays: Tic-Tac-Toe

Singly Linked Lists (SLL)

Time complexity

Circularly Linked Lists (CLL)

Rotate operation

Insert element at head

Time complexity

Doubly Linked Lists (DLL)

Inserting a node

Inserting at the front

Deleting a node

Methods

List ADT

Operations on a list

Array Lists

Dynamic array

Grow-Array($A, n$)

Amortized analysis of dynamic arrays

Shrinking the dynamic array

String vs. StringBuilder class

Positional Lists

Position or cursor

Access and update methods

Operations

Insertion sort