什么是線性表、順序表、鏈表

本篇內(nèi)容介紹了“什么是線性表、順序表、鏈表”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

首先來看一下線性表，順序表，和鏈表之間的區(qū)別和聯(lián)系：

• 線性表：

1. 邏輯結(jié)構(gòu)， 就是對(duì)外暴露數(shù)據(jù)之間的關(guān)系，不關(guān)心底層如何實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)大分類就是線性結(jié)構(gòu)和非線性結(jié)構(gòu)，而順序表、鏈表都是一種線性表。

2. 線性表結(jié)構(gòu)存儲(chǔ)的數(shù)據(jù)往往是可以依次排列的，就像小朋友手拉手，每位學(xué)生的前面和后面都僅有一個(gè)小朋友和他拉手，具備這種“一對(duì)一”關(guān)系的數(shù)據(jù)就可以使用線性表來存儲(chǔ)。

• 順序表、鏈表：物理結(jié)構(gòu)，他是實(shí)現(xiàn)一個(gè)結(jié)構(gòu)實(shí)際物理地址上的結(jié)構(gòu)。比如順序表就是用數(shù)組實(shí)現(xiàn)。而鏈表用指針完成主要工作。不同的結(jié)構(gòu)在不同的場(chǎng)景有不同的區(qū)別。

線性表

我們首先定義一個(gè)線性表的抽象類，主要包括增加、查找、刪除等方法。后面分別用順序表和鏈表做實(shí)現(xiàn)：

/**
 * 線性表
 *
 * @author ervin
 * @Date 2021/4/18
 */
public interface ListInterface<T> {

    /**
     * 初始化
     * @param size
     */
    void init(int size);

    /**
     * 長(zhǎng)度
     * @return
     */
    int length();


    /**
     * 是否為空
     * @return
     */
    boolean isEmpty();

    /**
     * 獲取元素下標(biāo)
     * @param t
     * @return
     */
    int eleIndex(T t);

    /**
     * 根據(jù)index獲取數(shù)據(jù)
     * @param index
     * @return
     * @throws Exception
     */
    T getEle(int index) throws Exception;

    /**
     * 根據(jù)index插入數(shù)據(jù)
     * @param index
     * @param t
     * @throws Exception
     */
    void add(int index,T t) throws Exception;

    /**
     * 刪除元素
     * @param index
     * @throws Exception
     */
    void delete(int index) throws Exception;

    /**
     * 尾部插入元素
     * @param t
     * @throws Exception
     */
    void add(T t) throws Exception;

    /**
     * 修改
     * @param index
     * @param t
     * @throws Exception
     */
    void set(int index,T t) throws Exception;
}

順序表

• 順序表是基于數(shù)組實(shí)現(xiàn)的，由于數(shù)組中的數(shù)據(jù)時(shí)存儲(chǔ)的一塊連續(xù)的內(nèi)存中，插入、刪除元素會(huì)導(dǎo)致部分元素的移動(dòng)，效率較低，但是查詢效率卻十分快。

順序表元素插入示意圖：

這里以插入為例做說明，刪除操作正好相反。

• 如果要?jiǎng)h除下標(biāo)為 2 的元素時(shí)，下標(biāo)為 2 及之后的元素，從左至右，依次左移一位。

• 另外，順序表的插入需要考慮 “擴(kuò)容”

代碼實(shí)現(xiàn)：

/**
 * 順序表實(shí)現(xiàn)
 *
 * @author ervin
 * @Date 2021/4/18
 */
public class SeqList<T> implements ListInterface<T> {

    //數(shù)組存放數(shù)據(jù)
    private Object[] date;

    private int length;

    public SeqList() {
        //初始大小默認(rèn)為10
        init(10);
    }

    @Override
    public void init(int initSize) {
        this.date = new Object[initSize];
        length = 0;
    }

    @Override
    public int length() {
        return this.length;
    }

    @Override
    public boolean isEmpty() {
        //是否為空
        return this.length == 0;
    }


    @Override
    public int eleIndex(T t) {
        for (int i = 0; i < date.length; i++) {
            if (date[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }


    @Override
    public T getEle(int index) throws Exception {
        if (index < 0 || index > length - 1) {
            throw new Exception("數(shù)值越界");
        }
        return (T) date[index];
    }

    @Override
    public void add(T t) throws Exception {
        //尾部插入
        add(length, t);
    }


    @Override
    public void add(int index, T t) throws Exception {
        if (index < 0 || index > length) {
            throw new Exception("數(shù)值越界");
        }
        //擴(kuò)容
        if (length == date.length) {
            Object[] newDate = new Object[length * 2];
            for (int i = 0; i < length; i++) {
                newDate[i] = date[i];
            }
            date = newDate;
        }
        //后面元素后移動(dòng)
        for (int i = length - 1; i >= index; i--) {
            date[i + 1] = date[i];
        }
        //插入元素
        date[index] = t;
        length++;

    }

    @Override
    public void delete(int index) throws Exception {
        if (index < 0 || index > length - 1) {
            throw new Exception("數(shù)值越界");
        }
        //index之后元素前移動(dòng)
        for (int i = index; i < length; i++) {
            date[i] = date[i + 1];
        }
        length--;
    }

    @Override
    public void set(int index, T t) throws Exception {
        if (index < 0 || index > length - 1) {
            throw new Exception("數(shù)值越界");
        }
        date[index] = t;
    }
}

鏈表

• 鏈表存儲(chǔ)數(shù)據(jù)的空間是不連續(xù)的，有一個(gè)個(gè) “node” 連接起來，形成鏈表，每一個(gè) “node” 不僅存放數(shù)據(jù)本身，還存放了下一個(gè) “node” 的地址。

如圖：

• 鏈表查找元素，需要遍歷查找，效率較低；插入刪除元素，只需要，修改指針，效率很高。

• 鏈表無需考慮 “擴(kuò)容”

鏈表元素插入示意：

鏈表元素刪除示意圖：

代碼實(shí)現(xiàn)：

/**
 * 鏈表實(shí)現(xiàn)
 *
 * @author ervin
 * @Date 2021/4/18
 */
public class LinkList<T> implements ListInterface<T> {


    private static class Node<T> {
        T item;
        Node<T> next;

        Node(T element, Node<T> next) {
            this.item = element;
            this.next = next;
        }
    }

    Node header;

    private int size;

    public LinkList(){
        this.header = new Node(null,null);
        this.size = 0;
    }

    @Override
    public void init(int size) {
    }

    @Override
    public int length() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.length() == 0;
    }

    @Override
    public int eleIndex(T t) {
        Node n = header.next;
        int index = 0;
        while (n.next != null){
            if (n.item.equals(t)){
                return index;
            }
            index++;
            n = n.next;
        }
        //找不到返回-1
        return -1;
    }

    @Override
    public T getEle(int index) throws Exception {
        Node n = getNode(index);
        return (T)n.item;
    }

    @Override
    public void add(int index, T t) throws Exception {
        //考慮第一個(gè)元素
        if (index == 0){
            this.header.next = new Node(t,null);
        } else {
            Node n = getNode(index - 1);
            //獲取到index的上一個(gè)元素n, n指向新建的元素，同時(shí)新建的元素指向n的下一個(gè)元素
            n.next = new Node(t,n.next);
        }
        this.size++;
    }

    @Override
    public void delete(int index) throws Exception {
        //index為0時(shí)，不用去獲取上一個(gè)元素，
        if (index == 0){
            this.header.next = getNode(1);
        } else {
            Node n = getNode(index - 1);
            n.next = n.next.next;
        }
        size--;
    }

    @Override
    public void add(T t) throws Exception {
        add(size,t);
    }

    @Override
    public void set(int index, T t) throws Exception {
        Node node = getNode(index);
        node.item = t;
    }

    private Node getNode(int index) throws Exception {
        if (index<0 || index > this.size-1){
            throw new Exception("數(shù)組越界");
        }
        Node n = header.next;
        for (int i = 0;i<index;i++){
            n = n.next;
        }
        return n;
    }
}

雙鏈表

在實(shí)際應(yīng)用中雙鏈表的應(yīng)用多一些，就比如LinkedList

雙鏈表的一個(gè)節(jié)點(diǎn)，有存儲(chǔ)數(shù)據(jù)的data，也有后驅(qū)節(jié)點(diǎn)next(指針)，指向下一個(gè)節(jié)點(diǎn)，這和單鏈表是一樣的，但它還有一個(gè)前驅(qū)節(jié)點(diǎn)pre(指針)，指向上一個(gè)節(jié)點(diǎn)。

• 這樣的設(shè)計(jì)，犧牲了額外的內(nèi)存類存儲(chǔ) “pre” 指針，但是相比單鏈表只能 “從頭向尾” 查找，雙鏈表不僅可以 “從頭向尾”，“從尾向頭”，甚至可以從中間開始查找，在有些時(shí)候，雙鏈表的查找效率要比單鏈表快很多。

這一點(diǎn)，在 JDK LinkedList 的源碼中有體現(xiàn)，我們來看它的 get(int index) 方法，

接著點(diǎn)進(jìn)去，看它的 node(int index) 方法

如果 index 位于鏈表的前半部分，則從前開始查找；反之，則從后開始查找。

總結(jié)

• 單鏈表查詢速度較慢，因?yàn)樗枰獜念^遍歷，插入刪除速度較快；內(nèi)存利用率高，不會(huì)浪費(fèi)內(nèi)存，大小沒有固定，拓展很靈活

• 順序表查詢速度較快，插入刪除速度較慢

• Java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優(yōu)化

• 雙鏈表的查詢速度要優(yōu)于單鏈表

• 從存儲(chǔ)結(jié)構(gòu)來看，每個(gè)雙鏈表的節(jié)點(diǎn)要比單鏈表的節(jié)點(diǎn)多一個(gè)指針，而長(zhǎng)度為n就需要 n*length（這個(gè)指針的length在32位系統(tǒng)中是4字節(jié)，在64位系統(tǒng)中是8個(gè)字節(jié)） 的空間，這在一些追求時(shí)間效率不高應(yīng)用下并不適應(yīng)，因?yàn)樗加每臻g大于單鏈表所占用的空間；這時(shí)設(shè)計(jì)者就會(huì)采用以時(shí)間換空間的做法，這是一種工程總體上的衡量。

“什么是線性表、順序表、鏈表”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！