java中數(shù)組與鏈表的比較

這篇文章主要講解了“java中數(shù)組與鏈表的比較”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“java中數(shù)組與鏈表的比較”吧！

目錄

• 數(shù)組與鏈表的比較：

• ArrayList：

• LinkedList：

• 總結(jié)

數(shù)組與鏈表的比較：

• 數(shù)組通過下標(biāo)訪問的話是O(1)

• 數(shù)組一旦聲明 長度就是固定的

• 數(shù)組的數(shù)據(jù)是物理邏輯均連續(xù)的

• 鏈表增刪要快一些, 數(shù)組遍歷快一些

• 長度一定的話， 數(shù)組的存儲空間比鏈表要小

ArrayList：

ArrayList是List接口的實現(xiàn)類，它是支持根據(jù)需要而動態(tài)增長的數(shù)組；java中標(biāo)準(zhǔn)數(shù)組是定長的，在數(shù)組被創(chuàng)建之后，它們不能被加長或縮短。這就意味著在創(chuàng)建數(shù)組時需要知道數(shù)組的所需長度，但有時我們需要動態(tài)程序中獲取數(shù)組長度。ArrayList就是為此而生的。

擴容機制發(fā)生在add()方法調(diào)用的時候；

  public boolean add(E e) {
       //擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

該行代碼ensureCapacityInternal()是用來擴用的，形參是最小擴容量，進入該方法后：

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

通過方法calculateCapacity(elementData, minCapacity)獲取:

   private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果傳入的是個空數(shù)組則最小容量取默認(rèn)容量與minCapacity之間的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

使用 ensureExplicitCapacity方法可以判斷是否需要擴容：

 private void ensureExplicitCapacity(int minCapacity) {
          modCount++;
          // 如果最小需要空間比elementData的內(nèi)存空間要大，則需要擴容
          if (minCapacity - elementData.length > 0)
              //擴容
              grow(minCapacity);
      }

需要擴容，進入ArrayList擴容的關(guān)鍵方法grow():擴大為原來的1.5倍；

 private void grow(int minCapacity) {
          // 獲取到ArrayList中elementData數(shù)組的內(nèi)存空間長度
          int oldCapacity = elementData.length;
         // 擴容至原來的1.5倍
         int newCapacity = oldCapacity + (oldCapacity >> 1);
         // 再判斷一下新數(shù)組的容量夠不夠，夠了就直接使用這個長度創(chuàng)建新數(shù)組，
          // 不夠就將數(shù)組長度設(shè)置為需要的長度
         if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
         //若預(yù)設(shè)值大于默認(rèn)的最大值檢查是否溢出
         if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
         // 調(diào)用Arrays.copyOf方法將elementData數(shù)組指向新的內(nèi)存空間時newCapacity的連續(xù)空間
         // 并將elementData的數(shù)據(jù)復(fù)制到新的內(nèi)存空間
         elementData = Arrays.copyOf(elementData, newCapacity);
     }

至此得出ArrayList擴容的本質(zhì)是計算出新的擴容數(shù)組的size后實例化，并將原有數(shù)組內(nèi)容復(fù)制到新數(shù)組中去。

LinkedList：

鏈表實現(xiàn)擴容，直接在尾指針后面加入新的元素即可。

實現(xiàn)LinkedList:LinkedList的底層實現(xiàn)是鏈表。更深理解是一個雙向鏈表。

節(jié)點代碼：

//節(jié)點
public class Node {
	Node previous;//前繼，指向前一個Node
	Object data;//節(jié)點數(shù)據(jù)
	Node next;//后繼，指向后一個Node
	public Node() {
	}
	public Node(Node previous, Object data, Node next) {
		super();
		this.previous = previous;
		this.data = data;
		this.next = next;
	} 
}

初始化MyLinkedList:

public class MyLinkedList {
	private Node first;//首節(jié)點
	private Node last;//尾節(jié)點
	private int size;//鏈表大小
	public MyLinkedList() {
		first = null;
		last = null;
		size = 0;
	}
}

尾部添加，實現(xiàn)add(Object obj)方法：

public void add(Object obj){
		Node node = new Node(null,null,null);
		if(first==null){//first=null,說明LinkedList中沒有一個節(jié)點
			node.data = obj;
			first = node;
			last = node;//第一個節(jié)點和最后一個節(jié)點都是node
			size++;
		}else{
			node.data = obj;
			last.next = node;//和最后一個連接起來
			node.previous = last;
			last = node;//當(dāng)前節(jié)點變?yōu)槟┪补?jié)點
			size++;
		}

現(xiàn)get(int index)方法，獲取index處的節(jié)點并返回Node:

使用循環(huán)，遍歷鏈表：

public Node get(int index) {
		RangeCheck(index);
		Node temp = null;
		if(index < (size>>1)){//改進的遍歷方法，右移運算符的巧用
			temp = first;
			for(int i=0;i<index;i++){
				temp = temp.next;
			}
		}else {
			temp = last;
			for(int i=size-1;i>index;i--){
				temp = temp.previous;
			}
		}
		return temp;
	}

任意位置插入，實現(xiàn)add(int index,Object obj)方法：插入的步驟注意順序，不要產(chǎn)生斷鏈。

public void add(int index,Object obj) {
		RangeCheck(index);//對傳入的索引必須進行檢查，判斷是否越界
		Node node = new Node(null,null,null);
		node.data = obj;
		Node node2=first;
		for(int i=0;i<index-1;i++){
			node2 = node2.next;
		}
		node.next = node2.next;
		node2.next.previous=node;
		node2.next = node;
		node.previous=node2;
		size++;
	}

RangeCheck():

private void RangeCheck(int index) {
		if(index<0||index >= size){
			throw new IndexOutOfBoundsException("IndexOutOfBounds"+index);//不合法則拋出異常
		}
	}

實現(xiàn)remove(Object obj)方法：

public boolean remove(Object obj) {
		Node node = first;
		if(obj==null){
			while(node!=null){
				if(node.data==null){
					removefast(node);
					return true;
				}
				node = node.next;
			}
		}else {
			while(node!=null){
				if(obj.equals(node.data)){
					removefast(node);
					return true;
				}
				node = node.next;
			}
		}
		return false;
	}
	private void removefast(Node node){
		node.previous.next=node.next;
		size--;
		node.data=null;
		node.previous = node.next = null;
	}

實現(xiàn)set(int index,Object obj)方法：

public Object set(int index,Object obj) {
		Node node = get(index);
		Object oldObject=node.data;
		node.data = obj;
		return oldObject;
	}

感謝各位的閱讀，以上就是“java中數(shù)組與鏈表的比較”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對java中數(shù)組與鏈表的比較這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！