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;
	}
}