範例詳解Java順序表和連結串列

本篇文章給大家帶來了關於的相關知識，其中主要介紹了關於順序表和連結串列的相關內容，順序表就是一個陣列，是用一段實體地址連續的儲存單元依次儲存資料元素的線性結構，下面一起來看一下，希望對大家有幫助。

程式設計師必備介面測試偵錯工具：

推薦學習：《》

1. 線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列。線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、連結串列、棧、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上並不一定是連續的，線性表在物理上儲存時，通常以陣列和鏈式結構的形式儲存。

2. 順序表

其實就是一個陣列。【增刪查改】那為什麼還有寫一個順序表，直接用陣列就好了嘛？不一樣，寫到類裡面將來就可以物件導向了。

2.1 概念及結構

順序表是用一段實體地址連續的儲存單元依次儲存資料元素的線性結構，一般情況下采用陣列儲存。在陣列上完成資料的增刪查改。

順序表一般可以分為：

靜態順序表：使用定長陣列儲存。
動態順序表：使用動態開闢的陣列儲存。

靜態順序表適用於確定知道需要存多少資料的場景.

靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用.

相比之下動態順序表更靈活, 根據需要動態的分配空間大小.

2.2 介面實現

我們來實現一個動態順序表. 以下是需要支援的介面.

這裡我們挨個拆解出來：

public class MyArrayList {

    public int[] elem;
    public int usedSize;//有效的資料個數

    public MyArrayList() {
        this.elem = new int[10];
    }
    // 列印順序表public void display() {
    
    }
    System.out.println();}// 獲取順序表長度public int size() {
    return 0;}// 在 pos 位置新增元素public void add(int pos, int data) {}// 判定是否包含某個元素public boolean contains(int toFind) {
    return true;}// 查詢某個元素對應的位置public int search(int toFind) {
    return -1;}// 獲取 pos 位置的元素public int getPos(int pos) {
    return -1;}// 給 pos 位置的元素設為 valuepublic void setPos(int pos, int value) {}//刪除第一次出現的關鍵字keypublic void remove(int toRemove) {}// 清空順序表public void clear() {}}
登入後複製

這是我們順序表的基本結構。下面我們就把順序表的功能一個一個拆解出來：

列印資料表：

public void display() {
    for (int i = 0; i < this.usedSize; i++) {
        System.out.print(this.elem[i] + " ");
    }
    System.out.println();}
登入後複製

獲取順序表長度：

public int size() {
    return this.usedSize;}
登入後複製

在 pos 位置新增元素：

public void add(int pos, int data) {
    if(pos < 0 || pos > this.usedSize) {
        System.out.println("pos 位置不合法");
        return;
    }
    if(isFull()){
        this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
    }
    for (int i = this.usedSize-1; i >= pos; i--) {
        this.elem[i + 1] = this.elem[i];
    }
    this.elem[pos] = data;
    this.usedSize++;}//判斷陣列元素是否等於有效資料個數public boolean isFull() {
    return this.usedSize == this.elem.length;}
登入後複製

判斷是否包含某個元素：

public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (this.elem[i] == toFind) {
            return true;
        }
    }
    return false;}
登入後複製

查詢某個元素對應的位置：

public int search(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (this.elem[i] == toFind) {
            return i;
        }
    }
    return -1;}
登入後複製

獲取 pos 位置的元素：

public int getPos(int pos) {
    if (pos < 0 || pos >= this.usedSize){
        System.out.println("pos 位置不合法");
        return -1;//所以 這裡說明一下,業務上的處理，這裡不考慮
    }
    if(isEmpty()) {
        System.out.println("順序表為空！");
        return -1;
    }
    return this.elem[pos];}//判斷陣列連結串列是否為空public boolean isEmpty() {
    return this.usedSize == 0;}
登入後複製

給 pos 位置的元素設為 value：

public void setPos(int pos, int value) {
    if(pos < 0 || pos >= this.usedSize) {
        System.out.println("pos 位置不合法");
        return;
    }
    if(isEmpty()) {
        System.out.println("順序表為空！");
        return;
    }
    this.elem[pos] = value;}//判斷陣列連結串列是否為空public boolean isEmpty() {
    return this.usedSize == 0;}
登入後複製

刪除第一次出現的關鍵字key：

public void remove(int toRemove) {
    if(isEmpty()) {
        System.out.println("順序表為空！");
        return;
    }
    int index = search(toRemove);//index記錄刪除元素的位置
    if(index == -1) {
        System.out.println("沒有你要刪除的數位！");
    }
    for (int i = index; i < this.usedSize - 1; i++) {
        this.elem[i] = this.elem[i + 1];
    }
    this.usedSize--;
    //this.elem[usedSize] = null;參照陣列必須這樣做才可以刪除}
登入後複製

清空順序表：

public void clear() {
    this.usedSize = 0;}
登入後複製

2.3 順序表的問題及思考

順序表中間/頭部的插入刪除，時間複雜度為O(N)
增容需要申請新空間，拷貝資料，釋放舊空間。會有不小的消耗。
增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以後增容到200，我們再繼續插入了5個資料，後面沒有資料插入了，那麼就浪費了95個資料空間。

思考： 如何解決以上問題呢？下面給出了連結串列的結構來看看。

3. 連結串列

3.1 連結串列的概念及結構

連結串列是一種物理儲存結構上非連續儲存結構，資料元素的邏輯順序是通過連結串列中的參照連結次序實現的。

實際中連結串列的結構非常多樣，如果按一般來分的話就是四種：

單向連結串列
雙向連結串列
迴圈連結串列
雙向迴圈連結串列

如果細分的話就有以下情況組合起來就有8種連結串列結構：

單向、雙向
帶頭、不帶頭
迴圈、非迴圈

這八種分別為：

單向帶頭迴圈
單向不帶頭迴圈
單向帶頭非迴圈
單向不帶頭非迴圈
雙向帶頭迴圈
雙向不帶頭迴圈
雙向帶頭非迴圈
雙向不帶頭非迴圈

注：上述加粗是我們重點需要學習的！！！

雖然有這麼多的連結串列的結構，但是我們重點掌握兩種:

無頭單向非迴圈連結串列：結構簡單，一般不會單獨用來存資料。實際中更多是作為其他資料結構的子結構，如雜湊桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。

head：裡面儲存的就是第一個節點(頭節點)的地址

head.next：儲存的就是下一個節點的地址

尾結點：它的next域是一個null

無頭雙向連結串列：在Java的集合框架庫中LinkedList底層實現就是無頭雙向迴圈連結串列。

最上面的數位是我們每一個數值自身的地址。
prev：指向前一個元素地址
next：下一個節點地址
data：資料

3.2 連結串列的實現

3.2.1無頭單向非迴圈連結串列的實現

上面地址為改結點元素的地址
val：資料域
next：下一個結點的地址
head：裡面儲存的就是第一個結點(頭結點)的地址
head.next：儲存的就是下一個結點的地址

無頭單向非迴圈連結串列實現:

class ListNode {
    public int val;
    public ListNode next;//ListNode儲存的是結點型別

    public ListNode (int val) {
        this.val = val;
    }}public class MyLinkedList {
    public ListNode head;//連結串列的頭參照

    public void creatList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;
    }
    //查詢是否包含關鍵字key是否在單連結串列當中
    public boolean contains(int key) {
        
        return true;
    }
    //得到單連結串列的長度
    public int size(){
        return -1;
    }
    //頭插法
    public void addFirst(int data) {

    }
    //尾插法
    public void addLast(int data) {

    }
    //任意位置插入,第一個資料節點為0號下標
    public boolean addIndex(int index,int data) {
        return true;
    }
    //刪除第一次出現關鍵字為key的節點
    public void remove(int key) {

    }
    //刪除所有值為key的節點
    public ListNode removeAllKey(int key) {

    }
    //列印連結串列中的所有元素
    public void display() {

    }
    //清除連結串列中所有元素
    public void clear() {
        
    }}
登入後複製

上面是我們連結串列的初步結構(未給功能賦相關程式碼，大家可以複製他們到自己的idea中進行練習，答案在下文中) 這裡我們將他們一個一個拿出來實現並實現！

列印連結串列中所有元素：

public void display() {
    ListNode cur = this.head;
    while(cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();}
登入後複製

查詢是否包含關鍵字key是否在單連結串列當中：

public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;}
登入後複製登入後複製

得到單連結串列的長度：

public int size(){
    int count = 0;
    ListNode cur = this.head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;}
登入後複製

頭插法(一定要記住繫結位置時一定要先繫結後面的資料避免後面資料丟失)：

public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = this.head;
    this.head = node;
    /*if (this.head == null) {
        this.head = node;
    } else {
        node.next = this.head;
        this.head = node;
    }*/}
登入後複製

尾插法：

public void addLast(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
    } else {
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }}
登入後複製

任意位置插入,第一個資料結點為0號下標(插入到index後面一個位置)：

/**
 * 找到index - 1位置的節點的地址
 * @param index
 * @return
 */public ListNode findIndex(int index) {
    ListNode cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    return cur;}//任意位置插入,第一個資料節點為0號下標public void addIndex(int index,int data) {
    if(index < 0 || index > size()) {
        System.out.println("index 位置不合法！");
        return;
    }
    if(index == 0) {
        addFirst(data);
        return;
    }
    if(index == size()) {
        addLast(data);
        return;
    }
    ListNode cur = findIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;}
登入後複製

注意：單向連結串列找cur時要-1，但雙向連結串列不用直接返回cur就好

刪除第一次出現關鍵字為key的結點：

/**
 * 找到 要刪除的關鍵字key的節點
 * @param key
 * @return
 */public ListNode searchPerv(int key) {
    ListNode cur = this.head;
    while(cur.next != null) {
        if(cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    return null;}//刪除第一次出現關鍵字為key的節點public void remove(int key) {
    if(this.head == null) {
        System.out.println("單連結串列為空");
        return;
    }
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    ListNode cur = searchPerv(key);
    if(cur == null) {
        System.out.println("沒有你要刪除的節點");
        return;
    }
    ListNode del = cur.next;
    cur.next = del.next;}
登入後複製

刪除所有值為key的結點：

public ListNode removeAllKey(int key) {
    if(this.head == null) {
        return null;
    }
    ListNode prev = this.head;
    ListNode cur = this.head.next;
    
    while(cur != null) {
        if(cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        } else {
            prev = cur;
            cur = cur.next;
        }
    }
        //最後處理頭
    if(this.head.val == key) {
        this.head = this.head.next;
    }
    return this.head;}
登入後複製

清空連結串列中所有元素：

public void clear() {
    while (this.head != null) {
        ListNode curNext = head.next;
        head.next = null;
        head.prev = null;
        head = curNext;
    }
    last = null;}
登入後複製登入後複製

3.2.2無頭雙向非迴圈連結串列實現：

上面的地址0x888為該結點的地址
val：資料域
prev：上一個結點地址
next：下一個結點地址
head：頭結點一般指向連結串列的第一個結點

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

    public ListNode (int val) {
        this.val = val;
    }}public class MyLinkedList {
    public ListNode head;//指向雙向連結串列的頭結點
    public ListNode last;//只想雙向連結串列的尾結點
    //列印連結串列
    public void display() {

    }
    //得到單連結串列的長度
    public int size() {
        return -1;
    }
    //查詢是否包含關鍵字key是否在單連結串列當中
    public boolean contains(int key) {
        return true;
    }
    //頭插法
    public void addFirst(int data) {

    }
    //尾插法
    public void addLast(int data) {

    }
    //刪除第一次出現關鍵字為key的節點
    public void remove(int key) {

    }
    //刪除所有值為key的節點
    public void removeAllKey(int key) {

    }
    //任意位置插入,第一個資料節點為0號下標
    public boolean addIndex(int index,int data) {
        return true;
    }
    //清空連結串列
    public void clear() {

    }}
登入後複製

列印連結串列：

public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();}
登入後複製

得到單連結串列的長度：

public int size() {
    ListNode cur = this.head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;}
登入後複製

查詢是否包含關鍵字key是否在單連結串列當中:

public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;}
登入後複製登入後複製

頭插法：

public void addFirst(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    } else {
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }}
登入後複製

尾插法：

public void addLast(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    } else {
        ListNode lastPrev = this.last;
        this.last.next = node;
        this.last = this.last.next;
        this.last.prev = lastPrev;
        /**
         * 兩種方法均可
         * this.last.next = node;
         * node.prev = this.last;
         * this.last = node;
         */
    }}
登入後複製

注：第一種方法是先讓last等於尾結點再讓他的前驅等於上一個地址而第二種方法是先使插入的尾結點的前驅等於上一個地址再使其等於尾結點

刪除第一次出現關鍵字為key的結點:

public void remove(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            if (cur == head) {
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    last = null;
                }
            } else if (cur == last) {
                last = last.prev;
                last.next = null;
            } else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
            return;
        }
        cur = cur.next;
    }}
登入後複製

刪除所有值為key的結點:

public void removeAllKey(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            if (cur == head) {
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    last = null;
                }
            } else if (cur == last) {
                last = last.prev;
                last.next = null;
            } else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
            //return;
        }
        cur = cur.next;
    }}
登入後複製

注：他和remove的區別就是刪除完後是不是直接return返回，如果要刪除所有的key值則不return，讓cur繼續往後面走。

任意位置插入,第一個資料節點為0號下標：

public void addIndex(int index,int data) {
    if (index < 0 || index > size()) {
        System.out.println("index 位置不合法");
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    ListNode cur = searchIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur;
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;}public ListNode searchIndex(int index) {
    ListNode cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return cur;}
登入後複製

思路：先判斷在頭位置就頭插在尾位置就尾插在中間就改變四個位置的值。

注意：單向連結串列找cur時要-1，但雙向連結串列不用直接返回cur就好

清空連結串列：

public void clear() {
    while (this.head != null) {
        ListNode curNext = head.next;
        head.next = null;
        head.prev = null;
        head = curNext;
    }
    last = null;}
登入後複製登入後複製

3.3 連結串列面試題

3.3.1反轉連結串列：

這裡的

cur = this.head;

prev = null;

curNext = cur.next;

public ListNode reverseList() {
    if (this.head == null) {
        return null;
    }
    ListNode cur = this.head;
    ListNode prev = null;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = prev;
        prev = cur;
        cur = curNext;
    }
    return prev;}
登入後複製

3.3.2找到連結串列的中間結點：

public  ListNode middleNode() {
    if (head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        if (fast == null) {
            return slow;
        }
        slow = slow.next;
    }
    return slow;}
登入後複製

3.3.3輸入一個連結串列返回該連結串列中倒數第k個結點

public ListNode findKthToTail(ListNode head,int k) {
    if (k <= 0 || head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (k - 1 != 0) {
        fast = fast.next;
        if (fast == null) {
            return null;
        }
        k--;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;}
登入後複製

3.3.4合併兩個連結串列並變成有序的

public  static  ListNode mergeTwoLists(ListNode headA,ListNode headB) {
    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;
    while (headA != null && headB != null) {
        if(headA.val <headB.val) {
            tmp.next = headA;
            headA = headA.next;
            tmp = tmp.next;
        } else {
            tmp.next = headB;
            headB = headB.next;
            tmp = tmp.next;
        }
    }
    if (headA != null) {
        tmp.next = headA;
    }
    if (headB != null) {
        tmp.next = headB;
    }
    return newHead.next;}
登入後複製

最後返回的是傀儡結點的下一個即newHead.next

3.3.5 編寫程式碼，以給定值x為基準將連結串列分割成兩部分，所有小於x的結點排在大於或等於x的結點之前。(即將所有小於x的放在x左邊，大於x的放在x右邊。且他們本身的排序不可以變)

//按照x和連結串列中元素的大小來分割連結串列中的元素public ListNode partition(int x) {
    ListNode bs = null;
    ListNode be = null;
    ListNode as = null;
    ListNode ae = null;
    ListNode cur = head;
    while (cur != null) {
        if(cur.val < x){
            //1、第一次
            if (bs == null) {
                bs = cur;
                be = cur;
            } else {
                //2、不是第一次
                be.next = cur;
                be = be.next;
            }
        } else {
            //1、第一次
            if (as == null) {
                as = cur;
                as = cur;
            } else {
                //2、不是第一次
                ae.next = cur;
                ae = ae.next;
            }
        }
        cur = cur.next;
    }
    //預防第1個段為空
    if (bs == null) {
        return as;
    }
    be.next = as;
    //預防第2個段當中的資料，最後一個節點不是空的。
    if (as != null) {
        ae.next = null;
    }
    return be;}
登入後複製

3.3.6 在一個排序的連結串列中，存在重複的結點，請刪除該連結串列中重複的結點，重複的結點不保留，返回連結串列頭指標。(有序的連結串列中重複的結點一定是緊緊挨在一起的)

public ListNode deleteDuplication() {
    ListNode cur = head;
    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;
    while (cur != null) {
        if (cur.next != null && cur.val == cur.next.val) {
            while (cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            //多走一步
            cur = cur.next;
        } else {
            tmp.next = cur;
            tmp = tmp.next;
            cur = cur.next;
        }
    }
    //防止最後一個結點的值也是重複的
    tmp.next = null;
    return newHead.next;}
登入後複製

3.3.7 連結串列的迴文結構。

public boolean chkPalindrome(ListNode head) {
    if (head == null) {
        return true;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //slow走到了中間位置
    ListNode cur = slow.next;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curNext;
    }
    //反轉完成
    while (head != slow) {
        if(head.val != slow.val) {
            return false;
        } else {
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    return true;}
登入後複製

3.3.8 輸入兩個連結串列，找出它們的第一個公共結點。

他是一個Y字形

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pl = headA;
    ListNode ps = headB;
    int lenA = 0;
    int lenB = 0;
    //求lenA的長度
    while (pl != null) {
        lenA++;
        pl = pl.next;
    }
    pl = headA;
    //求lenB的長度
    while (ps != null) {
        lenB++;
        ps = ps.next;
    }
    ps = headB;
    int len = lenA - lenB;//差值步
    if (len < 0) {
        pl = headB;
        ps = headA;
        len = lenB - lenA;
    }
    //1、pl永遠指向了最長的連結串列，ps永遠指向了最短的連結串列   2、求到了插值len步
    //pl走差值len步
    while (len != 0) {
        pl = pl.next;
        len--;
    }
    //同時走直到相遇
    while (pl != ps) {
        pl = pl.next;
        ps = ps.next;
    }
    return pl;}
登入後複製

3.3.9 給定一個連結串列，判斷連結串列中是否有環。

提問：為啥麼fast一次走兩步，不走三步？

答：如果連結串列只有兩個元素他們則永遠相遇不了(如上圖的範例2)，而且走三步的效率沒有走兩步的效率高。

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;}
登入後複製

3.3.10 給定一個連結串列，返回連結串列開始入環的第一個節點。如果連結串列無環，則返回 null

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }
    if (fast == null || fast.next == null) {
        return null;
    }
    fast = head;
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;}
登入後複製

4. 順序表和連結串列的區別和聯絡

4.1順序表和連結串列的區別

順序表：一白遮百醜

白：空間連續、支援隨機存取

醜：

中間或前面部分的插入刪除時間複雜度O(N)
增容的代價比較大。

連結串列：一(胖黑)毀所有

胖黑：以節點為單位儲存，不支援隨機存取

所有：

任意位置插入刪除時間複雜度為O(1)
沒有增容問題，插入一個開闢一個空間。

組織：

1、順序表底層是一個陣列，他是一個邏輯上和物理上都是連續的

2、連結串列是一個由若干結點組成的一個資料結構，邏輯上是連續的但是在物理上[記憶體上]是不一定連續的。

操作：

1、順序表適合，查詢相關的操作，因為可以使用下標，直接獲取到某個位置的元素

2、連結串列適合於，頻繁的插入和刪除操作。此時不需要像順序表一樣，移動元素。連結串列的插入只需要修改指向即可。

3、順序表還有不好的地方，就是你需要看滿不滿，滿了要擴容，擴容了之後，不一定都能放完。所以，他空間上的利用率不高。

4.2陣列和連結串列的區別

連結串列隨用隨取要一個new一個

而陣列則不一樣陣列是一開始就確定好的

4.3AeeayList和LinkedList的區別

集合框架當中的兩個類

集合框架就是將所有的資料結構，封裝成Java自己的類

以後我們要是用到順序表了直接使用ArrayList就可以。