Lecture 04 - 01/25

Linked List Data Structure with Java

Single Linked List (SLList): Improvement on IntList

/** An SLList is a list of integers. It hides the ugly inner workings. */
public class SLList {
private static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
/* The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
/** Creates an empty SLList.
* The constructors start off with a extra sentinel node (-1)
* so that when initializing SSList's with out passing parameters,
* we don't have an error (without this, we would need to assign
* null to an integer which we can't do). In this class, we will
* access and edit SLLists starting from sentiinel.next, ignoring
* the existence of this sentinel node. */
public SLList() {
sentinel = new IntNode(-1, null);
size = 0;
}
public SLList(int x) {
sentinel = new IntNode(-1, null);
sentinel.next = new IntNode(x, null);
size = 1;
}
/** Adds x to the front of the list. */
public void addFirst(int x) {
sentinel.next = new IntNode(x, sentinel.next);
size = size + 1;
}
/** Returns the first item in the list. */
public int getFirst() {
return sentinel.next.item;
}
/** Adds x to the end of the list. */
public void addLast(int x) {
size = size + 1;
IntNode p = sentinel;
/* Advance p to the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
/** Returns the ith item of this list. */
public int get(int i) {
IntNode p = sentinel;
/* Advance p to the ith position in list. */
while (i > 0) {
p = p.next;
i -= 1;
}
return p.next.item;
}
/** Returns the size of the list. */
public int size() {
return size;
}
public static void main(String[] args) {
/* Creates a list of one integer, namely 10 */
SLList L = new SLList();
L.addLast(1);
L.addLast(2);
L.addLast(3);
System.out.println(L.size());
int f = L.get(1);
}
}

SLList vs IntList: