Java：連結清單的基本操作

1、定義接口Link：

public interface Link {
	void add(Object obj);                //增加節點
	boolean remove(int index);           //删除指定節點
	boolean set(int index,Object obj);   //修改節點
	Object get(int index);               //查詢指定節點
	void printLink();                    //列印連結清單
	Object[] toArray();                  //将連結清單節點内容存入數組
	int getSize();                       //得到連結清單大小
	void clear();                        //清空連結清單
	int contains(Object obj);            //判斷obj是否存在于連結清單
}
           

2、定義LinkImpl類實作Link接口

public class LinkImpl implements Link {
	
	private Node first;
	private Node last;
	private int size;
	
//--------------------------
	private class Node{
		private Node prev;
		private Object data;
		private Node next;
		
		public Node(Node prev,Object data,Node next){
			this.prev = prev;
			this.data = data;
			this.next = next;
		}
	}
//--------------------------

	@Override
	public void add(Object obj) {
		Node lastNode = last;
		Node newNode = new Node(lastNode, obj, null);
		last = newNode;
		
		if(first == null) {
			first = newNode;
		}else {
			lastNode.next = newNode;
		}
		size++;
	}

	@Override
	public boolean remove(int index) {
		// TODO Auto-generated method stub
		if(index < 0 || index >= size) {
			return false;
		}
		else if(index == 0) {
			if(size == 1) {
				Node node = first;
				node = null;
				first = null;
				last = null;
				size--;
			}
			else {
				Node node = node(index);
				first = node.next;
				node.next.prev = null;
				node = null;
				size--;
			}
		}else if(index == size - 1) {
			Node node = node(index);
			last = node.prev;
			node.prev.next = null;
			node = null;
			size--;
		}else {
			Node node = node(index);
			node.prev.next = node.next;
			node.next.prev = node.prev;
			node = null;
			size--;
		}
		return true;
	}

	@Override
	public boolean set(int index, Object obj) {
		if(index < 0 || index >= size) {
			return false;
		}
		
		Node node = node(index);
		node.data = obj;
		
		return true;
	}
	
	private Node node(int index) {
		if(index < (size >> 1)) {
			Node temp = first;
			for(int i = 0;i < index;i++) {
				temp = temp.next;
			}
			return temp;
		}else {
			Node temp = last;
			for(int i = size - 1;i > index;i--) {
				temp = temp.prev;
			}
			return temp;
		}
	}

	@Override
	public Object get(int index) {
		// TODO Auto-generated method stub
		if(index < 0 || index >= size) {
			return null;
		}
		Object[] arr = toArray();
		return arr[index - 1];
	}

	@Override
	public void printLink() {
		Object[] arr = toArray();
		for(int i = 0;i < size;i++) {
			System.out.println(arr[i]);
		}
	}

	@Override
	public Object[] toArray() {
		Object[] arr = new Object[size];
		int i = 0;
		for(Node node = first;node != null;node = node.next) {
			arr[i++] = node.data;
		}
		return arr;
	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public void clear() {
		Node rubbish;
		for(Node node = first;node != null;node = rubbish) {
			node.prev = null;
			node.data = 0;
			rubbish = node.next;
			node.next = null;
		}
		first = null;
		last = null;
		size = 0;
	}

	@Override
	public int contains(Object obj) {
		int index = 0;
		for(Node node = first;node != null;node = node.next) {
			if(node.data == obj) {
				return index + 1;
			}
			index++;
		}
		return -1;
	}

}
           

3、定義Factory類得到LinkImpl類的一個對象

public class Factory {
	private Factory() {
		
	};
	public static Link getLinkInstance() {
		return new LinkImpl();
	}
}
           

4、使用者端測試類

public class Test {

	public static void main(String[] args) {
		Link link = Factory.getLinkInstance();
		link.add("火車頭");
		link.add("車廂1");
		link.add("車廂2");
		link.add("車廂3");
		link.add("車尾");
		
		link.printLink();
		link.set(2, "VIP車廂");
		System.out.println("*******************");
		link.printLink();
		System.out.println("*******************");
		System.out.println(link.get(3));
		System.out.println("*******************");
		System.out.println(link.contains("車廂3"));
		System.out.println(link.contains("車廂三"));
		System.out.println("*******************");
		System.out.println(link.getSize());
		System.out.println("*******************");
		link.clear();
		link.printLink();
		System.out.println("*******************");
		System.out.println(link.getSize());
		link.remove(4);
		link.printLink();
	}

}
           

測試結果：

火車頭
車廂1
車廂2
車廂3
車尾
*******************
火車頭
車廂1
VIP車廂
車廂3
車尾
*******************
VIP車廂
*******************
4
-1
*******************
5
*******************
*******************
0
           

完！