數組與鏈表

前言

數組和鏈表是兩種數據結構,數組非常簡單易用但是它有兩個非常大的缺點,一個是數組一旦創建無法擴展,另一個則是數組的查找和刪除的速度很慢.

鏈表改善了一些數組的缺點,但是同樣的鏈表自身也存在一些自己的缺點.

本篇博客將為大家介紹一下這數組和鏈表特點及各自的優缺點.

閱讀前的準備工作

,一種粗略的評價計算機算法效率的方法.後面的內容會用到表示效率的方法.

1. 數組

我們按數組中的數組是否排序對數組進行劃分,將數組分為無序數組和有序數組.無序數組中的數組是無序的,而有序數組中的數據則是升序或者降序排序的.

1.1 無序數組

因為無序數組中的數據是無序的,往數組中添加數據時不用進行比較和移動數據,所以往無序數組裡面添加數據很快.無論是添加第一個數據還是第一萬個數據所需的時間是相同的,效率為O(1).

至於查找和刪除速度就沒有那麼快了,以數組中有一萬個數據項為例,最少需要比較1次,最多則需要比較一萬次,平均下來需要比較5000次,即N/2次比較,N代表數據量,大O表示法中常數可以忽略,所以效率為O(N).

結論:

  1. 插入很快,因為總是將數據插入到數組的空餘位置.
  2. 查找和刪除很慢,假設數組的長度為N,那麼平均的查找/刪除的比較次數為N/2,並且還需要移動數據.

1.2 有序數組

無序數組中存放的數據是無序的,有序數組裡面存放的數據則是有序的(有可能是升序有可能是降序).

因為有序數組中的數據是按升序/降序排列的,所以插入的時候需要進行排序並且移動數據項,所有有序數組的插入速度比無序數組慢. 效率為O(N).

刪除速度和無序數組一樣慢 效率為O(N).

有序數組的查找速度要比無序數組快,這是因為使用了一個叫做二分查找的算法.

二分查找: 二分查找也稱折半查找(Binary Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須採用順序存儲結構,而且表中元素按關鍵字有序排列.

有一個關於二分查找的形象類比 -> 猜數遊戲

假設要在0-100之間猜一個數,那麼你第一個要猜的数字就是100的一半50的時候,你的朋友會告訴你這個数字比要猜的数字是大還是小,如果比数字大,你接下來要猜的数字就是50的一半25,你的朋友說比這個数字要大,那麼你下面要猜的数字就是25-50中間的那個數37,以此類推…

使用二分查找可極大的提高查找的效率,假設一個有序數組有十億個數據,那麼查找到所需的数字,最多只需比較30次.

有序數組使用二分查找的效率為O(logN).有序數組也可以通過二分查找來新增和刪除數據以提高效率,但是依然需要在新增/刪除后移動數據項,所以效率依然會有影響.

總結:

  1. 有序數組的查找速度比無序數組高,效率為O(logN)
  2. 有序數組的刪除和新增速度很慢,效率為O(N)

1.3 數組總結

數組雖然簡單易用,但是數組有兩個致命的缺點:

  1. 數組存儲的數量有限,創建的過大浪費資源,創建的過小溢出
  2. 數組的效率比其他數據結構低
  • 無序數組插入效率為O(1)時間,但是查找花費O(N)時間
  • 有序數組查找花費O(logN)時間,插入花費O(N)時間
  • 刪除需要移動平均半數的數據項,所以刪除都是O(N)的時間

2. 鏈表

數組一經創建大小就固定住了,無法修改,鏈表在這方面做出了改善,只要內存夠用就可以無限制的擴大.

鏈表是繼數組之後應用最廣泛的數據結構.

2.1 鏈表的特點

鏈表為什麼叫鏈表呢? 因為它保存數據的方式就像一條鎖鏈

鏈表保存數據的方式很像上面的這一條鎖鏈,每一塊鎖鏈就是一個鏈節點,鏈節點保存着自己的數據同時通過自己的next()方法指向下一個鏈節點. 鏈表通過鏈節點不斷地調用next()方法就可以遍歷鏈表中的所有數據.

在鏈表中,每個數據項都被包含在”鏈節點”(link)中,一個鏈結點是某個類的對象,這個類可以叫做Link.因為一個鏈表中有許多類似的鏈結點,所以有必要用一個不同於鏈表的類來表達鏈結點.

每個Link對象中都包含一個對下一個鏈結點引用的字段(通常叫做next).

鏈表本身的對象中有一個字段指向對第一個鏈結點的引用.

數據與鏈表查找數據的區別: 在數組中查找數據就像在一個大倉庫裏面一樣,一號房間沒有,我們去二號房間,二號房間沒有我們去三號房間,以此類推.. 按照地址找完所有房間就可以了.

而在鏈表中查找數據就像單線彙報的地下工作者,你是孤狼你想要彙報點情報給你的頂級上司毒蜂,但是你必須先報告給你的接頭人豬剛鬣,豬剛鬣在報告給它的單線接頭人土行孫,最後由土行孫報告給毒蜂.只能一個找一個,這樣最終完成任務.

2.2 Java代碼

鏈節點類:


/**
 * @author liuboren
 * @Title: 鏈節點
 * @Description:
 * @date 2019/11/20 19:30
 */
public class Link {
    //  保存的數據
    public int data;

    // 指向的下一個鏈節點
    public Link nextLink;

    public Link(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

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

    public Link getNextLink() {
        return nextLink;
    }

    public void setNextLink(Link nextLink) {
        this.nextLink = nextLink;
    }
}

鏈表類


/**
 * @author liuboren
 * @Title: 鏈表類
 * @Description:
 * @date 2019/11/20 19:31
 */
public class LinkList {
    private Link first;

    public LinkList() {
        first = null;
    }

    // 新增鏈節點方法
    public void insertFirst(int data) {
        Link link = new Link(data);
        link.setNextLink(first);
        first = link;
    }
}

在新增節點的時候,新增的link的next方法指向原來的first節點,並將鏈表類的first指向新增的節點.

2.4 其他鏈表

剛剛介紹的鏈表是單向鏈表,只能從后往前遍歷,其他的鏈表還有雙端鏈表、雙向鏈表、有序鏈表.

再簡單介紹一下雙端鏈表吧.

雙端鏈表就是在單向鏈表的基礎上,新增一個成員變量指向鏈表的最後一個對象.

雙端鏈表代碼:

/**
 * @author liuboren
 * @Title: 鏈表類
 * @Description:
 * @date 2019/11/20 19:31
 */
public class LinkList {
    private Link first;
    private Link last;

    public LinkList() {
        first = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    // 新增鏈節點方法
    public void insertFirst(int data) {
        Link newLink = new Link(data);
        newLink.setNextLink(first);
        if (isEmpty()) {
            last = newLink;
        }
        first = newLink;

    }
}

雙向鏈表則是可以從first和last兩個方向進行遍歷,有序鏈表的數據都是按照關鍵字的順序排列的,本文不再展開了.

2.5 鏈表的效率

鏈表的效率:

  • 表頭插入和刪除速度都很快,花費O(1)的時間.
  • 平均起來,查找&刪除&插入在制定鏈節點後面都需要搜索一半的鏈節點需要O(N)次比較,雖然數組也需要O(N)次比較,但是鏈表讓然要快一些,因為不需要移動數據(只需要改變他們的引用)

3. 總結

鏈表解決了數組大小不能擴展的問題,但是鏈表自身依然存在一些問題(在鏈表的鏈節點後面查找&刪除&插入的效率不高),那麼有沒有一種數據結構即擁有二者的優點又改善了二者的缺點呢,答案是肯定的,下篇博客將為您介紹這種優秀的數據結構,敬請期待.

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※想知道網站建置網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計後台網頁設計

※不管是台北網頁設計公司台中網頁設計公司,全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置台北網頁設計,各種案例分享

小三通物流營運型態?

※快速運回,大陸空運推薦?

您可能也會喜歡…