Java中的数据结构(2)----链表

单链表：

package com.wz.util;

class Node<T> {
	public T t;
	public Node<T> next;

	Node(T t) {
		this.t = t;
	}

	public String toString() {
		return t.toString();
	}
}

public class SingleList<T> {
	private Node<T> head;
	private int size;

	SingleList() {
		size = 0;
		head = new Node<T>(null); // 表头不放数据
		head.next = null;
	}

	// 插入到链表的前端(表头之后)
	public void insertHead(Node<T> n) {
		n.next = head.next;
		head.next = n;
		size++;
	}

	// 插入到链表的尾部(默认添加方式)
	public void insert(Node<T> n) {
		n.next = null;
		Node<T> current = head.next;
		while (current.next != null)
			current = current.next;
		current.next = n;
		size++;
	}

	// 在指定节点后添加节点
	public void insertTo(Node<T> n1, Node<T> n2) {
		n2.next = n1.next;
		n1.next = n2;
		size++;
	}

	// 删除链表前端节点
	public void delHead() {
		Node<T> current = new Node<T>(null);
		current = head.next;
		head.next = current.next;
		current = null;
		size--;
	}

	// 删除尾节点
	public void delTail() {
		Node<T> current = head.next;
		Node<T> prev = null;
		while (current.next != null) {
			prev = current;
			current = current.next;
		}
		prev.next = null;
		current = null;
		size--;
	}

	// 删除指定节点
	public void del(Node<T> n) {
		Node<T> current = head.next;
		Node<T> prev = null;
		if ((n != null) && (current == n))
			delHead();
		else {
			while ((current != n) && (current != null)) {
				prev = current;
				current = current.next;
			}
			prev.next = current.next;
			current = null;
			size--;
		}
	}
	// 链表长度
	public int getSize() {
		return size;
	}
	// 另外一种计算链表长度的方法
	public int length(){
		int leng = 0;
		Node<T> current = head.next;
		while(current != null){
			leng++;
			current = current.next;
		}
		return leng;
	}

	// 遍历链表并打印
	public void diplay() {
		Node<T> current = head.next;
		while (current != null) {
			System.out.println(current.toString());
			current = current.next;
		}
	}
}