Review of references

Recall that object types are references, thus you can have several classes such as:

class A {
	B next;
}
class B{
	C next;
}
class C{
}

In the above example, "A" objects by default have their next field set to "null". Similarly, "B" objects by default have their next field also set to null. Thus, creating an A does not automatically create a B nor a C. You would need the following statements in a function to connect all three together:

A a = new A();
a.next = new B();  //set the a.next reference to memory location of new object
a.next.next = new C(); //set the next reference in the "B" object a.next, set that to new C

The Linked List Node Class

Because fields are merely references, a class can reference an instance of itself. Later, we will connect multiple objects with these links. We call each of these objects, "Nodes":

class Node {
	int data;  // Some optional information associated with each object
	Node next; // a reference to another node
}

Linking several nodes

Once we have a node class with a "next" reference, you can create several nodes and connect them together:

//in some function somewhere:
Node a = new Node();
a.data = 10;
Node b = new Node();
b.data = 20;
Node c = new Node();
c.data = 30;
//Now we have 3 nodes, and we can connect them:
a.next = b;
b.next = c;

System.out.println(a.data);            //prints 10
System.out.println(a.next.data);       //prints 20
System.out.println(a.next.next.data);  //prints 30

System.out.println(a.next.next.next);  //null
//Note that if you tried a.next.next.next.data, 
//  ... you would get a NullPointerException

A generic Node class

We call objects linked linearly in a line a "Linked List". Often, we want to story arbitrary information with each node in the list. Although in the above example we had the field "int data", we may want to store other types. Thus, often the Node object is generic:

class Node<T> {  //T is the generic ("templated") type
	T data;
	Node<T> next;  //You need to re-specify the generic...
	               // when referencing the next node
}

Doubly linked lists

In the previous example, every object references the next object in the list. This is sometimes called a singly linked list. However, if we have each node also reference the previous object, this is called a doubly linked list. Here's an example doubly linked list node class:

class Node<T> {
	T data;
	Node<T> previous;
	Node<T> next;
	
	//Additionally here are some useful constructors and methods:
	Node(T d) {
		data = d;
	}
	T getData() {
		return data;
	}
	void setData(T d) {
		data = d;
	}
	Node<T> getNext() {
		return next;
	}
	Node<T> getPrevious() {
		return previous;
	}
	void setNext(Node<T> n) {
		next = n;
	}
	void setPrevious(Node<T> p) {
		previous = p;
	}
}

Creating a linked list class

Rather than individually interacting with nodes, we often want to treat the entire list as an object. We will create a class called MyLinkedList to represent this object, and then we will add methods to "add", "remove", and "get" items from this list. We will also need to be able to get the "size" of the list. Many more methods are provided by the java built in java.util.LinkedList class, but we will not cover them all here.

Creating a MyLinkedList class

A linked list can be tracked by just the first item in the list. Thus, one valid set of fields would look like this:

class Node<T> {
	T data;
	Node<T> previous, next;
}	
class MyLinkedList<T> {
	Node<T> head; //referencing the first item
}

However, later one this will require us to walk through each item in the list in order to find the last item. This will make adding items to the end of the list very slow. Thus, an alternative way of constructing a doubly linked list has both a head and tail reference:

class Node<T> {
	T data;
	Node<T> previous, next;
}	
class MyLinkedList<T> {
	Node<T> head; //referencing the first item
	Node<T> tail; //referencing the last item
}

Adding items to the list

To add items to a list, we have to handle two cases. In the case of an empty list (where the head and tail references are null), we need to set both the head and tail to the new node. Otherwise, we need to add the item after the tail, and set the tail to point to the newly created last item.

class Node<T> {
	T data;
	Node<T> prev, next;
}
class MyLinkedList<T> {
	Node<T> head, tail;
	void add(T data) {   //The new add method takes the data type T (not a node)
		Node<T> node = new Node<T>();  //It creates a Node
		node.data = data;   //It sets the data (this node has no alternate constructor)
		if(head == null) head = tail = node;  //if the list is empty, sets head/tail
		else {
			tail.next = node;  //otherwise, we stick the new node after the current tail
			node.prev = tail;
			tail = node;       //and re-assign the tail
		}
	}
}

Getting the size of a list

There are several ways of computing the size of a list. One way is to loop through the list and count the number of items. Alternatively, we can keep a variable that increases each time we add something to a list. This second way is faster, and here are both ways:

class Node<T> {
	T data;
	Node<T> prev, next;
}
class MyLinkedList<T> {
	Node<T> head, tail;
	int numNodes = 0;
	void add(T data) {
		Node<T> node = new Node<T>();
		node.data = data;
		if(head == null) head = tail = node;
		else {
			tail.next = node;
			node.prev = tail;
			tail = node;
		}
		numNodes++;  //increment numNodes for each add call
	}
	int size() {
		return numNodes;
	}
	int sizeSlow() {  //compute by looping through
		int out = 0;
		for(Node<T> cur = head; cur != null; cur = cur.next) {
			out++;
		}
		return out;
	}
}

Getting items from a list

To retrieve the data within a list, we need to locate the node at a particular index. Then, we can return the data at that node:

class Node<T> {
	T data;
	Node<T> prev, next;
}
class MyLinkedList<T> {
	Node<T> head, tail;
	int numNodes = 0;
	void add(T data) {
		Node<T> node = new Node<T>();
		node.data = data;
		if(head == null) head = tail = node;
		else {
			tail.next = node;
			node.prev = tail;
			tail = node;
		}
		numNodes++;
	}
	T get(int index) {  //The new get method
		Node<T> cur = head; //Walk down the list with cur
		for(int i = 0; i < index; i++) { //Walk down index times
			cur = cur.next;  
		}
		return cur.data;
	}
	int size() {
		return numNodes;
	}
}

Removing items from a list

The most complicated algorithm here is the removal of items from a list. To remove an item, we need to change the prev/next references of the items before and after. If the node is the first or last item, we also need to change the head or tail references:

class Node<T> {
	T data;
	Node<T> prev, next;
}
class MyLinkedList<T> {
	Node<T> head, tail;
	int numNodes = 0;
	void add(T data) {
		Node<T> node = new Node<T>();
		node.data = data;
		if(head == null) head = tail = node;
		else {
			tail.next = node;
			node.prev = tail;
			tail = node;
		}
		numNodes++;
	}
	T get(int index) {
		Node<T> cur = head;
		for(int i = 0; i < index; i++) {
			cur = cur.next;
		}
		return cur.data;
	}
	void remove(int index) {  //The new remove method
		//if we remove the only item:
		if(head == tail && index == 0) head = tail = null;
		else {
			Node<T> cur = head;
			for(int i = 0; i < index; i++) {
				cur = cur.next;
			}
			
			if(cur == head) { //if removing first item
				head = head.next;
				head.prev = null;
			}else if(cur == tail) { //removing last item
				tail = tail.prev;
				tail.next = null;
			}else {  //removing an item in the middle
				cur.next.prev = cur.prev;
				cur.prev.next = cur.next;
			}
		}
		numNodes--;
		//We could return the removed data here if we wanted to
	}
	int size() {
		return numNodes;
	}
}

Putting it all together

Now, we can use the MyLinkedList almost like we use the built in java.util.LinkedList: