list ADT

Work in Progress

Summary

List ADT

  • simple linear data structure
  • sequence where order matters

java.util.List interface

Library implemetations

java
import java.util.ArrayList;
import java.util.LinkedList;

List<Integer> A = new ArrayList<>();
// or
List<Integer> A = new LinkedList<>();
A.add(5);
A.add(10);
A.add(15);
A.add(25); // A = [5, 10, 15, 25]

// get(i)
int val = A.get(2); // 15

// search(v)
int idx = A.indexOf(10); // 1
// indexOf returns the index of first match or -1

// insert(i, v)
A.add(2, 20); // A = [5, 10, 20, 15, 25]

// remove(i)
A.remove(1); // A = [5, 20, 15, 25]

Concept

List operations

  • get(i)
    • return the value at index i
  • search(v)
    • return the index of v if found within the list
    • return -1 if not found
  • insert(i, v)
    • insert v into the list at index i
  • remove(i)
    • remove the value at index i from the list

Application