Archive Notes

Week 2. Linked Lists

2 min read

Week 2. Linked Lists

Java review

Data structure

Data structure: a systematic way of organising, accessing and updating data.

Link to original

Algorithm

An algorithm is a finite sequence of precise step-by-step instructions.

Link to original

Abstract Data Type

Abstract data type (ADT): model of a data structure that specifies the type of data stored, the operations supported on them, and the type of parameters of the operations. An ADT specifies what each operation does, but not how it does it.

Link to original

Example ADT: Stack data structure

An instance of the stack data structure is a sequence of elements (objects) with one end designated as the top of the stack:

Main stack operations:

  • push(e): insert element at the top of the stack
  • pop(): remove and return the element at the top of the stack

Additional stack operations:

  • top(): return the top element in stack (without removing)
  • size(): return number of elements stored
  • isEmpty(): indicates if the stack is empty
// Interface for Stack
public interface Stack<E> {
	public void push(E element);
	public E pop() throws EmptyStackException;
	public E top() throws EmptyStackException;
	public int size();
	public boolean isEmpty();
}
 
// Array-based stack implementation:
public class ArrayStack<E> implements Stack<E> {}
 
// Implementation of a stack based on a singly linked list:
public class NodeStack<E> implements Stack<E> {}
 
// Using an implementation of stack:
Stack<String> S = new NodeStack<String>();
S.push(...);

Singly Linked List

Linked List

A linked list is an alternative to arrays for storing a sequence of objects.

Link to original

Singly Linked List

A singly linked list is a sequence of nodes, each node stores: an element an a link to the next node.

Link to original

List Operations

Insert at Head

  1. Allocate a new node
  2. Insert new element
  3. Have new node point to old head
  4. Update head to point to new node
  5. Update “size”, if maintained
  6. If inserting to empty list, update tail, if maintained

Removing at Head

  1. Update head to point to next node in the list
  2. Update “size”, if maintained
  3. If the list is now empty, update tail, if maintained
  4. Return the removed element
  5. GC will reclaim the former first node

Inserting at Tail

  1. Allocate a new node
  2. Insert new element
  3. Have new node to point to null
  4. Have old last node point to new node (if list wasn’t empty)
  5. Update tail to point to new node
  6. If inserting to empty list, update head
  7. Update “size”, if maintained

Removing at Tail

Removing at the tail of a singly linked list is not efficient, there is no “constant-time” way to update the tail to point to the previous node.

Graph View