集合框架--双向链表的模拟实现

Java中的鏈表,分為三種:

      1.單向鏈表,由一個節點元素,可以找到相鄰的下一個節點元素.

      2.雙向鏈表,由一個節點元素,可以找到其相鄰的前/后節點元素.

      3.循環鏈表,由一個節點元素,可以找到其相鄰的前/后節點元素,由最后一個節點元素可以找到第一個節點元素.

有關Java的集合框架的相關知識,請參考 Java API,此處僅用示例來模擬集合框架中[雙向鏈表] 的實現.

 

1. 定義一個節點類

 

package collection;

public class Node {
	//下一個節點
	private Node next;
	//前一個節點
	private Node prev;
	//節點中的數據
	private Object data;

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}

	public Node getPrev() {
		return prev;
	}

	public void setPrev(Node prev) {
		this.prev = prev;
	}

	public Object getData() {
		return data;
	}

	public void setData(Object data) {
		this.data = data;
	}

}

 

2. 定義一個鏈表類

 

package collection;

public class LinkedNode {
	
	//首節點
	private Node firstNode = null;
	//節點的長度
	private int size = 0;

	//添加數據和節點
	public void put(Node node, Object data) {
		//將數據存入節點中
		node.setData(data);
		//設置節點的位置
		if (null == firstNode) {
			firstNode = node;
		} else {
			// 查找最后一个节点
			Node lastNode = firstNode;
			//
			while (null != lastNode.getNext()) {
				lastNode = lastNode.getNext();
			}
			//設置下一個節點
			lastNode.setNext(node);
			//設置前一個節點
			node.setPrev(lastNode);
		}
		size++;
	}

	//獲取指定位置的節點對象
	public Node get(int index) {
		Node node = firstNode;
		//
		if (index != 0) {
			do {
				node = node.getNext();
			} while (--index > 0);
		}
		return node;
	}

	//獲取節點長度
	public int size() {
		return size;
	}
}

 

3. 新建一個測試類

 

package collection;

public class LinkedListTest {
	public static void main(String[] args) {
		LinkedNode ln = new LinkedNode();
		//定義節點
		Node n1 = new Node();
		Node n2 = new Node();
		Node n3 = new Node();
		Node n4 = new Node();
		Node n5 = new Node();
		Node n6 = new Node();
		Node n7 = new Node();
		Node n8 = new Node();
		Node n9 = new Node();
		//往節點中存入數據
		ln.put(n1, "aa");
		ln.put(n2, "bb");
		ln.put(n3, "cc");
		ln.put(n4, "dd");
		ln.put(n5, "ee");
		ln.put(n6, "ff");
		ln.put(n7, "gg");
		ln.put(n8, "hh");
		ln.put(n9, "ii");
		
		Node n = ln.get(3);
		//當前的節點
		System.out.println("當前節點中數據:"+n.getData());

		//前一個節點
		Node p = n.getPrev();
		System.out.println("當前節點的前一個節點中數據:"+p.getData());

		//后一個節點
		Node next = n.getNext();
		System.out.println("當前節點的后一個節點中數據:"+next.getData());
	}
}

 

4. 運行結果如下