• <nav id="wkkge"><strong id="wkkge"></strong></nav>
  • <menu id="wkkge"></menu>
  • Java面向對象
    Java異常
    Java數組
    Java常用類
    Java集合
    Java IO流
    Java線程
    Java反射
    Socket編程
    Java注解開發
    Java GoF設計模式
    HashMap
    Java內存模型
    Java線性表

    線性表的鏈式存儲與實現

     

     

    單向鏈表

     

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

     

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

     

     

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

     

     

     

    通過單向鏈表實現線性表

     

    
    /**
     * 通過單向鏈表實現線性表
     * @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;
    		}
    	}
    	
    }
    

     

    全部教程
  • <nav id="wkkge"><strong id="wkkge"></strong></nav>
  • <menu id="wkkge"></menu>
  • 面对面棋牌游戏