01204212/codes/linked lists

from 01204212

LinkedList for integers

Methods removeHead and addAfter are left out as exercises.

public class LinkedList {

	public class Node {
		private int val;
		private Node next = null;

		public Node(int val) {
			this.val = val;
			this.next = null;
		}

		public Node() {
			this(0);
		}

		public Node getNext() {
			return next;
		}

		public int getVal() {
			return val;
		}

		public void setVal(int v) {
			val = v;
		}
	}

	private Node head = null;
	private Node tail = null;
	private int size = 0;

	public LinkedList() {
		head = tail = null;
		size = 0;
	}

	public boolean isEmpty() {
		return tail != null;
	}

	public int size() {
		return size;
	}

	public Node addHead(int v) {
		if (isEmpty()) {
			return add(v);
		} else {
			Node newNode = new Node(v);
			newNode.next = head;
			head = newNode;
			return newNode;
		}
	}

	public void removeHead() {
		// ... 
	}

	public Node add(int v) {
		Node newNode = new Node(v);

		if (!isEmpty()) {
			tail.next = newNode;
			tail = newNode;
		} else {
			head = tail = newNode;
		}

		size++;
		return newNode;
	}

	public Node addAfter(Node node, int v) {
		// ... 
	}

	public void removeAfter(Node node) {
		if (node.next != null) {
			node.next = node.next.next;
			size--;
		}
	}

	public Node getHead() {
		return head;
	}
}

Generic linked lists (no iterator)

public class LinkedList<T> {

	public class Node {
		private T val;
		private Node next = null;

		public Node(T val) {
			this.val = val;
			this.next = null;
		}

		public Node() {
			this(null);
		}

		public Node getNext() {
			return next;
		}

		public T getVal() {
			return val;
		}

		public void setVal(T v) {
			val = v;
		}
	}

	private Node head = null;
	private Node tail = null;
	private int size = 0;

	public LinkedList() {
		head = tail = null;
		size = 0;
	}

	public boolean isEmpty() {
		return tail != null;
	}

	public int size() {
		return size;
	}

	public Node addHead(T v) {
		if (isEmpty()) {
			return add(v);
		} else {
			Node newNode = new Node(v);
			newNode.next = head;
			head = newNode;
			return newNode;
		}
	}

	public void removeHead() {
		// ... 
	}

	public Node add(T v) {
		Node newNode = new Node(v);

		if (!isEmpty()) {
			tail.next = newNode;
			tail = newNode;
		} else {
			head = tail = newNode;
		}

		size++;
		return newNode;
	}

	public Node addAfter(Node node, T v) {
		// ...
	}

	public void removeAfter(Node node) {
		if (node.next != null) {
			node.next = node.next.next;
			size--;
		}
	}

	public Node getHead() {
		return head;
	}
}

Generic list (with iterator)

public class LinkedList<T> {

	private class Node {
		private T val;
		private Node next = null;

		public Node(T val) {
			this.val = val;
			this.next = null;
		}

		public Node() {
			this(null);
		}

		public Node getNext() {
			return next;
		}

		public T getVal() {
			return val;
		}

		public void setVal(T v) {
			val = v;
		}
	}

	public class Iterator {
		private Node currentNode;
		private LinkedList<T> list;
		
		Iterator(Node node, LinkedList<T> list) {
			currentNode = node;
			this.list = list;
		}
		
		T getVal() {
			return currentNode.getVal();
		}
		
		void next() {
			currentNode = currentNode.getNext();
		}

		public Iterator add(T v) {
			Node newNode = new Node(v);
			newNode.next = currentNode.next;
			currentNode.next = newNode;

			list.size++;
			return new Iterator(newNode, list);
		}

		public void removeAfter() {
			// ...
		}	
	}
	
	private Node head = null;
	private Node tail = null;
	private int size = 0;

	public LinkedList() {
		head = tail = null;
		size = 0;
	}

	public boolean isEmpty() {
		return tail != null;
	}

	public int size() {
		return size;
	}

	public Iterator addHead(T v) {
		if (isEmpty()) {
			return add(v);
		} else {
			Node newNode = new Node(v);
			newNode.next = head;
			head = newNode;
			return new Iterator(newNode, this);
		}
	}

	public void removeHead() {
		if (head != null) {
			head = head.next;
			size--;

			if (head == null) {
				tail = null;
			}
		}
	}

	public Iterator add(T v) {
		Node newNode = new Node(v);

		if (!isEmpty()) {
			tail.next = newNode;
			tail = newNode;
		} else {
			head = tail = newNode;
		}

		size++;
		return new Iterator(newNode, this);
	}

	public Iterator iterator() {
		return new Iterator(head, this);
	}
}