線性表的鏈式存儲與實現

單向鏈表

單向鏈表 ,即單鏈表. 每個存儲單元至少有兩個存儲域, 一個用來存儲數據, 一個域保存下個存儲單元的引用。

各個存儲單元的地址可以是不連續的。

插入/刪除時不需要移動元素

通過單向鏈表實現線性表

/**
 * 通過單向鏈表實現線性表
 * @author 北京動力節點老崔
 */

public class MySingleLink implements MyList {
	private Node head;			//頭結點
	private int size; 			//保存元素的個數
	
	// 返回元素的個數
	@Override
	public int getSize() {
		return size;
	}

	// 判斷線性表是否為空
	@Override
	public boolean isEmpty() {
		return size == 0 ;
	}

	// 在線性表中插入元素
	@Override
	public void insert(int i, Object e) {
		//判斷索引值是否越界
		if ( i < 0 || i > size) {
			throw new IndexOutOfBoundsException(i+"越界");
		}
		//創建結點
		Node newNode = new Node(e, null);
		//頭結點為null的情況,鏈表不存在, 剛剛添加的結點就是頭結點
		if (head == null) {
			head = newNode; 
		}else {
			//在0位置插入結點
			if (i == 0 ) {
				newNode.next = head; 		//修改新結點的next域指向原來的頭結點
				head = newNode;			//剛插入的結點就是新的頭結點
			}else {
				//插入結點, 先找到i-1這個結點
				Node pNode = head; 
				for( int x = 1; x<i; x++) {
					pNode = pNode.next; 
				}
				//注意,先修改新結點的next指針域, 再修改i-1結點的指針域
				newNode.next = pNode.next;
				pNode.next = newNode;
			}
		
		}
		//元素個數加0
		size++;
	}

	// 判斷線性表中是否包含指定的元素
	@Override
	public boolean contains(Object e) {
		return indexOf(e) >= 0 ;
	}

	// 返回元素e在線性表中第一次出現的索引值
	@Override
	public int indexOf(Object e) {
		int i  = 0  ;		//保存元素e的索引值
		Node pNode = head; 
		while( pNode != null) {
			if ( e == null && pNode.data == null) {
				return i;
			}else if (e != null && e.equals(pNode.data)) {
				return i;
			}
			i++;
			pNode = pNode.next;
		}
		return -1;
	}

	//從線性表中刪除第一個與e相同的元素
	@Override
	public Object remove(Object e) {
		//找到元素e第一次出現的索引值
		int index = indexOf(e);
		if (index < 0 ) {
			return null; 		//元素不存在
		}
		return remove(index);
	}

	//從線性表中刪除指定索引的元素
	@Override
	public Object remove(int i) {
		//判斷是否越界
		if (i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i + "越界");
		}
		Node pNode = head;
		//刪除頭結點
		if (i == 0) {
			head = head.next;
			size--;
			return pNode.data; 		//返回刪除頭結點的數據
		}
		//找到i-1結點
		for( int x = 1; x < i ; x++) {
			pNode = pNode.next;
		}
		//
		Object old = pNode.next.data; 		//保存刪除結點的數據
		pNode.next = pNode.next.next;		//修改i-1結點的next指針域 ,指向 i+1結點
		size--;
		
		return old;
	}

	// 把線性表中i索引值的元素替換 為e
	@Override
	public Object replace(int i, Object e) {
		//判斷是否越界
		checkIndex(i);
		
		//找到i結點
		Node pNode = getNode(i);
		Object old = pNode.data ;		//保存原來的數據
		pNode.data = e;		//替換
		return old;
	}

	// 返回線性表中i索引值的元素
	@Override
	public Object get(int i) {
		checkIndex(i);
		Node pNode = getNode(i);
		return pNode.data;
	}
	//檢查索引值是否越界
	private void checkIndex(int i ) {
		if (i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i + "越界");
		}
	}
	
	//定義一個方法,返回i索引值的元素
	private Node getNode(int i) {
		if ( i < 0 || i >= size) {
			return null;
		}
		if (i == 0) {
			return head;
		}
		//找到i結點
		Node pNode = head;
		for( int x = 1; x <= i ; x++) {
			pNode = pNode.next;
		}
		return pNode;
	}

	// 在指定的元素p的前面插入元素e
	@Override
	public boolean insertBefore(Object p, Object e) {
		//找p的位置
		int index = indexOf(p);
		if (index < 0 ) {
			return false; 		//元素p不存在
		}
		insert(index, e);
		return true;
	}
	// 在指定的元素p的后面插入元素e
	@Override
	public boolean insertAfter(Object p, Object e) {
		// 找p的位置
		int index = indexOf(p);
		if (index < 0) {
			return false; // 元素p不存在
		}
		insert(index+1, e);
		return true;
	}

	//重寫toString()
	@Override
	public String toString() {
		// 把鏈表中各個結點的數據域連接起來
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		Node pNode = head;
		while(pNode != null) {
			sb.append(pNode.data);
			//使用逗號分隔
			if (pNode.next != null) {
				sb.append(",");
			}
			pNode = pNode.next; 		//指針下移
		}
		sb.append("]");
		return sb.toString();
	}
	//定義一個內部類表示單向鏈表中的結點
	private class Node{
		Object data;		//保存數據
		Node next;			//下個結點的引用
		public Node(Object data, Node next) {
			super();
			this.data = data;
			this.next = next;
		}
		
		
	}
}

雙向鏈表

單向鏈表只能通過一個結點的引用訪問它的后續結點, 不能訪問前驅結點, 如果要找某個 結點的前驅結點, 需要從頭結點開始依次查找。

在雙向鏈表中,擴展了結點的結構, 每個 結點除了存儲數據外, 通過一個引用指向后續結點,再定義一個引用指向前驅結點：

雙向鏈表的結構:

插入元素

雙向鏈表實現線性表

/**
 * 雙向鏈表
 * @author 北京動力節點老崔
 */
public class MyDualLinkedList implements MyList {
	private  Node first; 			//指向頭結點
	private  Node last; 			//指向尾結點
	private int  size; 				//保存元素的個數
	
	// 返回元素的個數
	@Override
	public int getSize() {
		return size;
	}

	// 判斷鏈表是否為空
	@Override
	public boolean isEmpty() {
		return size == 0 ;
	}

	// 在指定的索引值插入元素
	@Override
	public void insert(int i, Object e) {
		//1)檢查索引值是否越界
		if (i < 0 || i > size) {
			throw  new IndexOutOfBoundsException(i + "越界");
		}
		//2) 如果i==0,  在頭部添加元素
		if ( i == 0 ) {
			addFirst(e);
		}else if( i == size ) {
			//3) 如果i==size, 在尾部添加元素
			addLast(e);
		}else {
			//4) 找到i結點, 在i結點的前面插入元素
			Node pNode = getNode(i);
			Node prevNode = pNode.prev;
			//生成新的結點
			Node newNode = new Node(e, prevNode, pNode);
			//修改前驅結點的后續			
			prevNode.next = newNode;
			pNode.prev = newNode;
			size++;
		}
	}

	//返回索引值對應的結點
	private Node getNode(int i) {
		// 
		Node pNode = first;
		for( int x = 0 ; x < i; x++) {
			pNode = pNode.next;
		}
		return pNode;
	}

	

	// 判斷鏈表 中是否包含指定的元素e, 如果存在返回true
	@Override
	public boolean contains(Object e) {
		return indexOf(e) >= 0;
	}

	// 判斷元素e在鏈表中第一次出現的位置, 如果不存在該元素返回-1
	@Override
	public int indexOf(Object e) {
		int i = 0 ; 			//保存元素e在鏈表中的索引值
		//依次遍歷鏈表中的各個結點, 比較結點的元素與指定的e是否一樣
		if (e == null) {
			for( Node  pNode = first;  pNode != null ; pNode = pNode.next) {
				if ( pNode.data == null ) {
					return i;
				}
				i++;
			}
		}else {
			for( Node  pNode = first;  pNode != null ; pNode = pNode.next) {
				if ( e.equals(pNode.data) ) {
					return i;
				}
				i++;
			}
		}
		return -1;
	}

	// 從鏈表中刪除指定的元素, 并返回刪除的元素
	@Override
	public Object remove(Object e) {
		//找到元素e對應的索引值
		int index = indexOf(e);
		if ( index < 0 ) {
			return null; 			 
		}
		return remove(index);
	}

	// 從鏈表中刪除指定索引值的元素, 并返回刪除的元素
	@Override
	public Object remove(int i) {
		//判斷索引值是否越界
		checkIndex(i);
		//找到i對應的結點
		Node pNode = getNode(i);
		Node prevNode = pNode.prev; 		//刪除結點的前驅
		Node nextNode = pNode.next; 		//刪除結點的后續
		
		if ( prevNode == null) {
			//刪除的頭結點
			first = nextNode;
		}else {
			prevNode.next = nextNode;
		}
		
		if ( nextNode == null) {
			//刪除尾結點
			last = prevNode;
		}else {
			nextNode.prev = prevNode;
		}
		
		size--; 				//修改元素個數
		
		return pNode.data;
	}

	//檢查索引值是否越界
	private void checkIndex(int i) {
		if ( i < 0 || i >= size ) {
			throw new IndexOutOfBoundsException(i + "越界");
		}
	}

	// 修改指定索引值的元素, 把原來的元素返回
	@Override
	public Object replace(int i, Object e) {
		//檢查索引值是否越界
		checkIndex(i);
		
		//找到索引值為i的結點
		Node pNode = getNode(i);
		Object oldData = pNode.data;
		pNode.data = e; 	//修改結點的元素
		return oldData;
	}

	// 返回指定索引值的元素
	@Override
	public Object get(int i) {
		//檢查索引值越界
		checkIndex(i);
		//找到索引值為i的結點
		Node pNode = getNode(i);
		return pNode.data;
	}

	// 在指定的元素p前面插入元素e
	@Override
	public boolean insertBefore(Object p, Object e) {
		//找到p元素在鏈表中的位置
		int index = indexOf(p);
		if (index < 0) { 			//鏈表中不存在元素p
			return false;
		}
		insert(index, e);  		//在p元素的前面插入元素e
		return true;
	}

	// 在指定的元素p后面插入元素e
	@Override
	public boolean insertAfter(Object p, Object e) {
		// 找到p元素在鏈表中的位置
		int index = indexOf(p);
		if (index < 0) { // 鏈表中不存在元素p
			return false;
		}
		insert(index + 1, e);  // 在p元素的后面插入元素e
		return true;
	}

	@Override
	public String toString() {
		// 依次遍歷各個結點,把元素轉換為字符串
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		
		for( Node node = first ;  node != null ; node = node.next) {
			sb.append( node.data );
			//元素之間使用逗號分隔
			if ( node != last ) {
				sb.append(",");
			}
		}
		
		sb.append("]");
		return sb.toString();
	}
	
	//在鏈表中,經常會有針對頭元素與尾元素的操作// 在鏈表的尾部添加元素
	public void addLast(Object e) {
		Node pNode = last;
		//生成一個新的結點
		Node newNode = new Node(e, last, null);
		if (pNode == null ) {
			first = newNode;
		}else {
			pNode.next = newNode;
		}
		last = newNode ;
		size++;
	}

	//在頭部添加元素e
	public void addFirst(Object e) {
		Node pNode = first;    
		// 生成一個新的結點
		Node newNode = new Node(e, null, first);		
		first = newNode; 		//修改first指向新的結點
		if ( pNode == null ) {
			last = newNode;
		}else {
			pNode.prev = newNode;
		}
		size++; 		//元素的個數加1 
	}
	
	//刪除第一個元素, 刪除頭元素
	public Object removeFirst() {
		return remove(0);
	}
	//刪除最后一個元素(尾元素)
	public Object removeLast() {
		return remove(size-1);
	}
	//返回頭元素
	public Object getFirst() {
		return get(0);
	}
	//返回最后一個元素
	public Object getLast() {
		return get(size-1);
	}
	

	//定義一個內部類描述雙向鏈表的結點
	private class Node {
		Object data;
		Node prev;			//指向前驅結點
		Node next;			//指向后繼結點
		public Node(Object data, Node prev, Node next) {
			super();
			this.data = data;
			this.prev = prev;
			this.next = next;
		}
	}
	
}