JAVA数据结构之链表

链表：单链表，双链表，循环链表

 

单链表：每个节点有一个内容和一个地址，这个地址指向下一个节点。

第一个加入链表的节点为头结点，它的地址指向第二个节点，第二个节点地址指向第三个节点。。。最后一个节点的地址指向null。

如图所示：

 

 

由这样的关系，我们容易得知只要知道first，我们就可以用first.next.next.....取到每一个节点元素。

对于单链表，我们要实现他的创建，添加，插入，删除，查询（遍历）等方法。

下面的程序只实现了基本的创建与遍历。其余均在双链表会实现。方法类似。

Node.java

package 单链表LinkedList的实现;

/**
 * 节点 包括 内容，地址
 * 
 * @author Huangbin
 *
 */
public class Node<E> {

	E elem;// 节点中的内容

	Node<E> next;// 对下一个节点的引用（下个节点也是Node类型的）

	public Node(E elem) {
		this.elem = elem;
	}

	public String toString() {
		return (String) elem;
	}
}

LinkList.java

package 单链表LinkedList的实现;

public class LinkList {

	public static void main(String[] args) {
		LinkList list = new LinkList();
		Node<String> node = list.creat();
		list.print2(node);
	}

	public Node<String> creat() {
		Node<String> node = new Node<String>("1");
		Node<String> node2 = new Node<String>("2");
		Node<String> node3 = new Node<String>("3");
		Node<String> node4 = new Node<String>("4");

		node.next = node2;
		node2.next = node3;
		node3.next = node4;

		return node;
	}

	/**
	 * 用循环遍历
	 * 
	 * @param head
	 */
	public void print(Node head) {
		Node node = head;
		while (node != null) {
			System.out.println(node);
			node = node.next;
		}
	}

	/**
	 * 用递归遍历
	 * 
	 * @param head
	 */
	public void print2(Node head) {
		if (head != null) {
			System.out.println(head);
			print2(head.next);// 递归 调用本身
		}
	}
}


运行结果：
1
2
3
4

 

双链表：

每个节点包含三部分，指向前一个元素的地址，内容，指向后一个元素的地址。每两个节点都会互相指向对方，一般习惯把第一个加进链表的节点成为头节点。最后一个为尾节点

关系如图所示

 

双链表的插入说明：（删除类似）


 

 

 

在双链表中，实现了一些常用的方法。具体见代码：

package 双链表LinkedList的实现;

import java.util.NoSuchElementException;

/**
 * 双链表
 * @author Huangbin 
 * d2014年7月17日
 * @param <E>
 */
public class LinkList<E> {

	Node<E> first;
	Node<E> last;
	private int length = 0;
	static LinkList list;

	public static void main(String[] args) {
		long t1 = System.currentTimeMillis();
		list = new LinkList<String>();
		list.test();
		long t2 = System.currentTimeMillis();
		System.out.println(t2 - t1);
	}

	public void test() {

		Node<Integer> node = new Node<Integer>(1);
		Node<Character> node2 = new Node<Character>('a');
		Node<Double> node3 = new Node<Double>(3.01);
		Node<Float> node4 = new Node<Float>(0.11f);// 8有效数字
		Node<Byte> node5 = new Node<Byte>((byte) 5);
		Node<String> node6 = new Node<String>("字符串6");
		Node<Boolean> node7 = new Node<Boolean>(true);
		Node<Boolean> node8 = new Node<Boolean>(false);
		Node<Boolean> node9 = new Node<Boolean>(false);
		Object arr[];
		list.add(node);
		list.add(node2);
		list.add(node3);
		list.add(node4, 3);
		list.add(node5);
		list.add(node6);
		list.add(node7);
		list.removeLast();
		list.printHead(first);
		arr = list.toArray();
		for (int i = 0; i < length; i++) {
			System.out.println(arr[i]);
		}
		System.out.println("Size: " + length);
	}

	public void printHead(Node<E> first) {
		if (first != null) {// 存在元素
			System.out.print(first.front);
			System.out.print("\t" + first);
			System.out.println("\t" + first.next);
			printHead(first.next);// 递归 调用本身
		}
	}

	/**
	 * 添加元素
	 * 
	 * @param node
	 */
	public void add(Node<E> node) {
		if (first != null) {// 已经存在元素了
			node.front = last;
			last.next = node;
		} else {
			// 添加第一个节点 头尾均指向第一个节点
			first = node;
		}
		last = node;// 重新指向最后一个节点
		length++;
	}

	/**
	 * 在指定位置插入新的元素
	 * 
	 * @param node
	 * @param num
	 */
	public void add(Node<E> node, int num) {
		if (num > length || num < 0) {
			throw new IndexOutOfBoundsException("Index: " + num + ", Size: "
					+ length);
		}
		if (num == 0) {
			if (first != null) {
				node.next = first;
				first.front = node;
				first = node;
			} else {
				add(node);// 不存在直接加进去。
			}
		} else if (num == length) {
			add(node);
		} else {

			Node<E> temp = first;
			for (int i = 1; i < num; i++) {
				temp = temp.next;
			}
			// 此时，temp指向了num位置
			node.front = temp;
			node.next = temp.next;
			temp.next.front = node;
			temp.next = node;
		}
	}

	/**
	 * 移除指定元素
	 * 
	 * @param node
	 */
	public Node<E> remove(Node<E> node) {
		// 先判断是否在链表中
		if (this.contains(node)) {
			// 遍历链表找到node元素的front与next改变他们的指向

			if (node.front != null && node.next != null) {// node是中间位置的元素

				node.next.front = node.front;
				node.front.next = node.next;// node前一个元素指向node的下一个元素

			} else if (node.next != null) {// 被移除的是第一个元素，且存在下一个元素
				first = node.next;
				first.front = null;
			} else if (node.front != null) {// 被移除的是最后一个元素，且存在下一个元素
				last = node.front;
				last.next = null;
			} else {// 移除最后一个元素了，node的前后都是空
				last = first = null;// 这个时候全部被移除了
			}
			// 清空node，释放资源
			// node.next = null;
			// node.front = null;
			// node.elem = null;
			length--;
			return node;
		} else {
			try {
				throw new Exception("不存在 \"" + node + "\" 元素！");
			} catch (Exception e) {
				e.printStackTrace();
			}
			return null;
		}
	}

	/**
	 * 移除指定下标的元素
	 * 
	 * @param num
	 */
	public Node<E> remove(int num) {
		if (num >= length || num < 0) {
			throw new IndexOutOfBoundsException("index:" + num + ",size:"
					+ length);
		}
		Node<E> node = first;
		for (int i = 0; i < num; i++) {
			node = node.next;
		}
		remove(node);
		return node;
	}

	/**
	 * 移除函相同内容的第一个指定元素
	 * 
	 * @return
	 */
	public Node<E> remove(Object o) {
		// 先判断是否在链表中
		if (this.contains(o)) {
			return remove((get(indexOf(o))));
		}
		return null;
	}

	/**
	 * 移除第一个元素
	 * 
	 * @return
	 */
	public Node<E> removeFirst() {
		if (first == null)
			throw new NoSuchElementException();
		return remove(first);
	}

	/**
	 * 移除最后一个元素
	 * 
	 * @return
	 */
	public Node<E> removeLast() {
		if (last == null)
			throw new NoSuchElementException();
		return remove(last);
	}

	/**
	 * 修改指定元素的内容
	 * 
	 * @param str
	 * @param num
	 */
	public void set(E o, int num) {
		get(num).elem = o;
	}

	/**
	 * 获得num下标位置的元素
	 * 
	 * @param num
	 * @return
	 */
	public Node<E> get(int num) {
		if (num >= length || num < 0) {
			throw new IndexOutOfBoundsException("Index: " + num + ", Size: "
					+ length);
		}
		Node<E> node = first;
		for (int i = 0; i < num; i++) {
			node = node.next;
		}

		return node;
	}

	/**
	 * 获得第一个元素
	 * 
	 * @return
	 */
	public Node<E> getFirst() {
		return first;
	}

	/**
	 * 获得最后一个元素
	 * 
	 * @return
	 */
	public Node<E> getLast() {
		return last;
	}

	/**
	 * 获得链表的长度
	 * 
	 * @return
	 */
	public int getSize() {
		return length;
	}

	/**
	 * 添加元素到链表头
	 * 
	 * @param node
	 */
	public void addFirst(Node<E> node) {
		add(node, 0);
	}

	/**
	 * 添加元素到链表尾
	 * 
	 * @param node
	 */
	public void addLast(Node<E> node) {
		add(node);
	}

	/**
	 * 查找元素内容o在哪个位置，不存在返回-1
	 * 
	 * @param o
	 * @return
	 */
	public int indexOf(Object o) {
		int index = 0;
		if (o == null) {
			for (Node<E> x = first; x != null; x = x.next) {
				if (x.elem == null || x == null) {
					return index;
				}
				index++;
			}
		} else {
			for (Node<E> x = first; x != null; x = x.next) {
				if (o.equals(x.elem) || o.equals(x)) {
					return index;
				}

				index++;
			}
		}
		return -1;
	}

	/**
	 * 是否有包含内容o的元素
	 * 
	 * @param o
	 * @return
	 */
	public boolean contains(Object o) {
		return indexOf(o) != -1;
	}

	/**
	 * 队列式取出首元素，先进先出
	 * 
	 * @return
	 */
	public Node<E> queuePop() {
		return removeFirst();
	}

	/**
	 * 栈式取出首元素，后进先出
	 * 
	 * @return
	 */
	public Node<E> statckPop() {
		return removeLast();
	}

	/**
	 * 放元素进去
	 * 
	 * @param node
	 */
	public void push(Node<E> node) {
		add(node);
	}

	/**
	 * 复制该链表
	 */
	public LinkList<E> clone() {
		LinkList<E> clone = new LinkList<E>();
		clone.first = clone.last = null;
		clone.length = 0;
		for (Node<E> node = first; node != null; node = node.next) {
			clone.add(node);

		}
		return clone;
	}

	/**
	 * 把链表转为数组
	 * 
	 * @return
	 */
	public Object[] toArray() {
		Object[] o = new Object[length];
		int i = 0;
		for (Node<E> x = first; x != null; x = x.next, i++) {
			o[i] = x.elem;
		}
		return o;
	}

	private class Node<E> {

		E elem;// 节点中的内容

		Node<E> front;// 对上一个节点的引用（上个节点也是Node类型的）
		Node<E> next;// 对下一个节点的引用（下个节点也是Node类型的）

		public Node(E elem) {
			this.elem = elem;
		}

		public String toString() {
			return (String) "" + elem;//便于打印
		}
	}

}
运行结果：
null	1	a
1	a	3.01
a	3.01	0.11
3.01	0.11	5
0.11	5	字符串6
5	字符串6	null
1
a
3.01
0.11
5
字符串6
Size: 6
3