Java全面講解順序表與鏈表的使用

更新時(shí)間：2022年05月07日 14:12:39 作者：菜菜不恰菜

大家好，今天給大家?guī)?lái)的是順序表和鏈表，我覺(jué)得順序表還是有比較難理解的地方的，于是我就把這一塊的內(nèi)容全部整理到了一起，希望能夠給剛剛進(jìn)行學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人帶來(lái)一些幫助，或者是已經(jīng)學(xué)過(guò)這塊的朋友們帶來(lái)更深的理解，我們現(xiàn)在就開(kāi)始吧

線性表

線性表（ linear list ）是 n 個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn) 的線性表：順序表、鏈表、棧、隊(duì)列、字符串 ... 線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)（內(nèi)存上）上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組（在物理上是連續(xù)的）和鏈?zhǔn)浇Y(jié)構(gòu)（在物理上不連續(xù)）的形式存儲(chǔ)。

順序表

順序表是用一段物理地址連續(xù) 的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。（可以說(shuō)順序表就相當(dāng)于一個(gè)數(shù)組）

那么問(wèn)題來(lái)了，為什么不直接使用數(shù)組，而要把數(shù)組放在類當(dāng)中，然后再對(duì)數(shù)組進(jìn)行操作？因?yàn)閿?shù)組沒(méi)有面向?qū)ο螅褦?shù)組放進(jìn)類當(dāng)中，可通過(guò)對(duì)象對(duì)它進(jìn)行操作。

聽(tīng)著概念有點(diǎn)模糊，接下來(lái)通過(guò)模擬順序表的接口實(shí)現(xiàn)來(lái)認(rèn)識(shí)一下順序表：

??用Arraylist來(lái)模擬實(shí)現(xiàn)順序表ArrayList的接口實(shí)現(xiàn)：

Arraylist:

public class Arraylist{
    public int[] arr;
    public int useSize;//數(shù)組有效個(gè)數(shù)
    public Arraylist() {
        this.arr = new int[10];//假設(shè)數(shù)組長(zhǎng)度為10
    }
    //打印順序表
    public void display() {
        for (int i = 0; i < this.useSize; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
    public boolean isFull() {
        return this.arr.length == this.useSize;
    }
    // 在 pos 位置新增元素
    public void add(int pos, int date) {
        if (pos < 0 || pos > useSize) {
            System.out.println("pos位置不合法"+" ");
            return;
        }
        if (isFull()) {
            this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);
        }
        for (int i = this.useSize - 1; i >= pos; i--) {
            this.arr[i + 1] = this.arr[i];
        }
        this.arr[pos] = date;
        this.useSize++;
    }
    // 判定是否包含某個(gè)元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.useSize; i++) {
            if (arr[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    // 查找某個(gè)元素對(duì)應(yīng)的位置
    public int search(int toFind) {
        for (int i = 0; i < this.useSize; i++) {
            if (arr[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
    // 獲取 pos 位置的元素
    public int getPos(int pos) {
        if (pos < 0 || pos >=useSize){
            System.out.println("pos位置不合法"+" ");
            return -1;//萬(wàn)一順序表中有-1這個(gè)元素怎么辦，后期說(shuō)
        }
        if(isEmpty()){
            System.out.print("順序表為空");
            return -1;
        }
        for (int i = 0; i < this.useSize; i++) {
            if (i == pos) {
                return this.arr[i];
            }
        }
        return -1;
    }
    public boolean isEmpty(){
        return this.useSize==0;
    }
    // 給 pos 位置的元素設(shè)為 value
    public void setPos(int pos, int value) {
        if (pos < 0 || pos >=useSize){
            System.out.print("pos位置不合法"+" ");
            return;
        }
        if(isEmpty()){
            System.out.println("順序表為空");
            return;
        }
                this.arr[pos] = value;
    }
    //刪除第一次出現(xiàn)的關(guān)鍵字key
    public void remove(int toRemove){
        if(isEmpty()) {//判斷順序表是否為空
            System.out.println("順序表為空");
        }
        int x=search(toRemove);
        if(x==-1){
            System.out.println("沒(méi)有你要?jiǎng)h除的數(shù)字");
            return;
        }
                for (int j = x; j<=this.useSize-1; j++) {
                    this.arr[j]=this.arr[j+1];
                }
        this.useSize--;
    }
    //清空順序表
    public void clear() {
        this.usedSize = 0;
  }
}

在pos位置新增元素：

判斷是否包含某個(gè)元素：

查找pos位置：

在pos位置上給值value

刪除第一次出現(xiàn)的關(guān)鍵字key

鏈表

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)(內(nèi)存）上非連續(xù) 存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的引用鏈接次序?qū)崿F(xiàn)的。實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有 8 種鏈表結(jié)構(gòu)：

單向、雙向

帶頭、不帶頭

循環(huán)、非循環(huán)

接下來(lái)主要講兩種：?jiǎn)蜗虿粠ь^非循環(huán)、雙向不帶頭非循環(huán)

??鏈表接口的模擬實(shí)現(xiàn)（單向不帶頭非循環(huán)）：鏈表是由一個(gè)一個(gè)節(jié)點(diǎn)組成，單向不帶頭非循環(huán)鏈表每個(gè)節(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，用來(lái)存放數(shù)據(jù)，另一個(gè)是存放下一個(gè)節(jié)點(diǎn)的地址。

class ListNode{//創(chuàng)建節(jié)點(diǎn),鏈表是由一個(gè)一個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)有兩個(gè)域組成，數(shù)據(jù)域和下一個(gè)節(jié)點(diǎn)地址組成
     public int val;
     public ListNode next;//沒(méi)有初始化默認(rèn)為null
     public ListNode(int val){
         this.val=val;
     }
}
//模擬實(shí)現(xiàn)單向不帶頭非循環(huán)鏈表的接口實(shí)現(xiàn)，用MyLinkedList模擬實(shí)現(xiàn)LinkedList
public class MyLinkedList {
    public ListNode head;//創(chuàng)建頭節(jié)點(diǎn)
    public void createList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(88);
        ListNode listNode3 = new ListNode(36);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        this.head = listNode1;//頭節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)地址
    }
    public void display() {
        ListNode cur;
        cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //頭插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if (cur == null) {
            this.head = node;
        } else {
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    //找到index-1下標(biāo)位置
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
    public void addIndex(int index, int data) {
        if(index<0||index>size()){
            System.out.println("輸入位置不合法");
            return;
        }
        if(index==0){//頭插
            this.addFirst(data);
            return;
        }
        if(index==size()){//尾插
            this.addLast(data);
            return;
        }
            ListNode cur = findIndex(index);
            ListNode node = new ListNode(data);
            node.next = cur.next;
            cur.next = node;
    }
    public boolean contains(int key) {
        return false;
    }
    public ListNode findremove(int key){
    ListNode cur=this.head.next;
    while(cur!=null) {
        if (cur.next.val == key) {
            return cur;
        } else {
            cur=cur.next;
        }
    }
    return null;
    }
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
    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 = findremove(key);//找到關(guān)鍵字上一個(gè)節(jié)點(diǎn)所在位置，并返回該節(jié)點(diǎn)
        if (cur == null) {
            System.out.println("沒(méi)找到關(guān)鍵字");
            return;
        }
            ListNode del=cur.next;
            cur.next=del.next;
        return;
    }
    //刪除所有值為key的節(jié)點(diǎn)
    public ListNode removeAllKey(int key) {
        if(this.head==null){
            return null;
        }
        ListNode per=this.head;
        ListNode cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                per.next=cur.next;
                cur=cur.next;
            }
            else{
                per=cur;
                cur=cur.next;
            }
        }
        if(this.head.val==key){
            this.head=this.head.next;
        }
        return this.head;
    }
    //得到單鏈表的長(zhǎng)度
    public int size() {
        ListNode cur=this.head;
        int count=0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
   //清除鏈表
    public void clear() {
        //this.head=null;//簡(jiǎn)單粗暴寫(xiě)法，當(dāng)一個(gè)節(jié)點(diǎn)沒(méi)有被指向時(shí)，就沒(méi)意義了
       //遍歷
        while(this.head!=null){
         ListNode curNext=this.head.next;
         this.head.next=null;
         this.head=curNext;
        }
    }
}

創(chuàng)建節(jié)點(diǎn)：

以上說(shuō)的鏈表是指單向不帶頭非循環(huán)鏈表?。?！

初始化鏈表：

打印鏈表：

頭插法：

尾插法：

任意位置插入一個(gè)數(shù)據(jù)：

刪除關(guān)鍵字key所在節(jié)點(diǎn)位置：

刪除所有值為key的節(jié)點(diǎn)：

雙向不帶頭非循環(huán)：

這種鏈表至少有三個(gè)域組成，一個(gè)是數(shù)據(jù)域，一個(gè)是存放上一個(gè)節(jié)點(diǎn)的位置，一個(gè)存放下一個(gè)節(jié)點(diǎn)的位置，雙向比單向的好處就體現(xiàn)出來(lái)了，雙向鏈表只要知道當(dāng)前節(jié)點(diǎn)位置，就可以對(duì)鏈表進(jìn)行增刪查改，而單相鏈表還需要知道當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)。

接口模擬實(shí)現(xiàn)：

//雙向不帶頭非循環(huán)
//創(chuàng)建節(jié)點(diǎn)
class ListNode{
    int val;
    ListNode prev;//前一個(gè)節(jié)點(diǎn)地址
    ListNode next;//下一個(gè)節(jié)點(diǎn)地址
    public ListNode(int val){
        this.val=val;
    }
        }
public class myLinkedList {
    public ListNode head;//頭節(jié)點(diǎn)
    public ListNode last;//尾節(jié)點(diǎn)
 
    //得到雙向鏈表長(zhǎng)度
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;//如果鏈表為空。返回0，所以這里可再單獨(dú)判斷也可不單獨(dú)判斷
    }
 
    //打印雙向鏈表
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
 
    //查找是否包含關(guān)鍵字在鏈表中
    public boolean contain(int key) {
        if (this.head == null) {
            return false;
        }
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
                cur = cur.next;
        }
        return false;
    }
 
    //刪除第一次出現(xiàn)的關(guān)鍵字
    public void remove(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {//第一種：關(guān)鍵字是在頭節(jié)點(diǎn)
                    this.head = this.head.next;
                    if (this.head != null) {
                        head.prev = null;
                    } else {//如果鏈表為空1情況下，要保證最后一個(gè)節(jié)點(diǎn)也要為空
                        this.last = null;
                    }
                } else {//第二種情況：關(guān)鍵字在中間或者結(jié)尾
                    cur.prev.next = cur.next;
                    if (cur.next != null) {//中間
                        cur.next.prev = cur.prev;
                    } else {
                        last = cur.prev;//結(jié)尾
                    }
                }
                return;
            }
            cur=cur.next;
        }
    }
 
    //刪除所有值為key的節(jié)點(diǎn)
    public void removeAllkey(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {//第一種：關(guān)鍵字是在頭節(jié)點(diǎn)
                    this.head = cur.next;
                    if (this.head != null) {
                        cur.next.prev = null;
                    } else {//如果鏈表為空1情況下，要保證最后一個(gè)節(jié)點(diǎn)也要為空
                        this.last = null;
                    }
                } else {//第二種情況：關(guān)鍵字在中間或者結(jié)尾
                    cur.prev.next = cur.next;
                    if (cur.next!=null) {//中間
                        cur.next.prev = cur.prev;
                    }
                    last = cur.prev;//結(jié)尾
                }
            }
            cur=cur.next;
        }
    }
 
    //頭插法
    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;
        }
        this.last.next=node;
        node.prev=this.last;
        this.last=node;
    }
    //任意位置插入，第一個(gè)數(shù)據(jù)節(jié)點(diǎn)下標(biāo)為0
    public ListNode search(int index){//尋找插入的位置
      ListNode cur=this.head;
      while(index!=0){
          cur=cur.next;
          index--;
      }
      return cur;
    }
    public void addIndex(int index,int data){
        ListNode node=new ListNode(data);
        if(index<0||index>size()){
            System.out.println("坐標(biāo)違法");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
 
        ListNode cur=search(index);
        node.next=cur.prev.next;
        cur.prev.next=node;
        node.prev=cur.prev;
        cur.prev=node;
        return;
    }
    //清除鏈表
    public void clear(){
        while(this.head!=null){
            ListNode curNext=this.head.next;
            this.head.prev=null;
            this.head.next=null;
            this.head=curNext;
        }
        last=null;
    }
}

查找是否包含關(guān)鍵字在鏈表中：