现在的位置: 首页 > 综合 > 正文

JAVA实现双向链表

2014年01月27日 ⁄ 综合 ⁄ 共 2300字 ⁄ 字号 评论关闭

JAVA实现双向链表

 

class DoubleLinkedList {
	/**
	 * 节点类Node
	 */
	private static class Node {
		Object value;
		Node prev = this;
		Node next = this;

		Node(Object v) {
			value = v;
		}

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

	private Node head = new Node(null); // 头节点
	private int size; // 链表大小

	// 以下是接口方法
	public boolean addFirst(Object o) {
		addAfter(new Node(o), head);
		return true;
	}

	public boolean addLast(Object o) {
		addBefore(new Node(o), head);
		return true;
	}

	public boolean add(Object o) {
		return addLast(o);
	}

	public boolean add(int index, Object o) {
		addBefore(new Node(o), getNode(index));
		return true;
	}

	public boolean remove(int index) {
		removeNode(getNode(index));
		return true;
	}

	public boolean removeFirst() {
		removeNode(head.next);
		return true;
	}

	public boolean removeLast() {
		removeNode(head.prev);
		return true;
	}

	public Object get(int index) {
		return getNode(index).value;
	}

	public int size() {
		return size;
	}

	public String toString() {
		StringBuffer s = new StringBuffer("[");
		Node node = head;
		for (int i = 0; i < size; i++) {
			node = node.next;
			if (i > 0)
				s.append(", ");
			s.append(node.value);
		}
		s.append("]");
		return s.toString();
	}

	// 以下是实现方法

	private Node getNode(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException();
		Node node = head.next;
		for (int i = 0; i < index; i++)
			node = node.next;
		return node;
	}

	private void addBefore(Node newNode, Node node) {
		newNode.next = node;
		newNode.prev = node.prev;
		newNode.next.prev = newNode;
		newNode.prev.next = newNode;
		size++;
	}

	private void addAfter(Node newNode, Node node) {
		newNode.prev = node;
		newNode.next = node.next;
		newNode.next.prev = newNode;
		newNode.prev.next = newNode;
		size++;
	}

	private void removeNode(Node node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
		node.prev = null;
		node.next = null;
		size--;
	}
}
// 有些地方还可以优化,比如查找时可以判断索引是否大于size的一半,如果是的话,就从另一头开始迭代。

 

/**
 * 可以用这个类测试一下
 */
public class Test {
	public static void main(String[] args) {
		DoubleLinkedList dll = new DoubleLinkedList();
		// 添加
		dll.add("张曼玉");
		dll.add("钟楚红");
		dll.add("刘嘉玲");
		System.out.println(dll);

		// 添加到最前
		dll.addFirst("林青霞");
		System.out.println(dll);

		// 添加到最后
		dll.addLast("梅艳芳");
		System.out.println(dll);

		// 添加到指定位置
		dll.add(4, "王祖贤");
		System.out.println(dll);

		// 移除最前的
		dll.removeFirst();
		System.out.println(dll);

		// 移除最后的
		dll.removeLast();
		System.out.println(dll);

		// 移除指定位置上的
		dll.remove(2);
		System.out.println(dll);

		// 返回指定位置上的元素
		System.out.println(dll.get(1));

	}
}

 

参考链接:
http://blog.csdn.net/fenglibing/article/details/669456
http://mountain-king.iteye.com/blog/717340
http://www.cnblogs.com/xilifeng/archive/2012/10/06/2713185.html#_Toc337310064

 

抱歉!评论已关闭.