欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實現(xiàn)順序表和鏈表結(jié)構(gòu)

 更新時間:2022年02月11日 08:46:51   作者:?????*  
大家好,本篇文章主要講的是Java實現(xiàn)順序表和鏈表結(jié)構(gòu),感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下

前言:

線性表(linear list)是n個具有相同特性的數(shù)據(jù)元素的有限序列。

線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu),常見的線性表:順序表、鏈表、棧、隊列、字符串。

順序表

定義:

用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)(邏輯上連續(xù),物理上也連續(xù))

(1)靜態(tài)順序表:使用定長數(shù)組存儲。

(2)動態(tài)順序表:使用動態(tài)開辟的數(shù)組存儲

【注意】靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了,空間開多了浪費,開少了不夠用,所以相比之下,動態(tài)數(shù)組更為靈活,可根據(jù)需要動態(tài)分配空間大小

實現(xiàn)方法:

增、刪、改、查

增加操作:從頭部插入、從尾部插入、在任意索引位置處插入

刪除操作:根據(jù)索引刪除元素、根據(jù)元素值刪除第一個出現(xiàn)的該元素、根據(jù)元素值刪除所有該值元素 

查找操作:根據(jù)元素值查找是否存在某元素、根據(jù)索引下標(biāo)返回該處元素值、根據(jù)元素值返回索引下標(biāo) 

修改操作:根據(jù)索引下標(biāo)修改該處元素 

代碼實現(xiàn):

public class MyArray {
    private int[]data;
    private int size;
//    無參構(gòu)造
    public MyArray(){
        this.data=new int[5];
    }
//    有參構(gòu)造
    public MyArray(int n){
        this.data=new int[n];
    }
//    grow方法用于擴充內(nèi)存
    private void grow() {
        int[] newdata= Arrays.copyOf(data,size*2);
        this.data=newdata;
    }
//    toString方法輸出順序表內(nèi)容
    public String toString(){
        String str="[";
        for (int i = 0; i <size ; i++) {
            str+=data[i];
            if(i!=size-1){
            str+=",";
            }
        }
        str+="]";
        return str;
    }
//    尾插法:
    public void addLast(int value){
        if(size== data.length){
            grow();
        }
        data[size]=value;
        size++;
    }
//    頭插法:
    public void addFirst(int value){
        if(size==data.length){
            grow();
        }
        for (int i = size-1; i >=0; i--) {
            data[i+1]=data[i];
        }
        data[0]=value;
        size++;
    }
//    中間任意位置插入:
    public void addIndex(int index,int value){
        if(size==data.length)
            grow();
        if(index<0||index>size){
            System.err.println("插入位置不合理!");
            return;
        }
        else {
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = value;
            size++;
        }
    }
//    查看當(dāng)前數(shù)組中是否存在該元素
    public boolean contains(int value){
        for (int i = 0; i < size; i++) {
            if(data[i]==value)
                return true;
        }
        return false;
    }
//    查找當(dāng)前數(shù)組元素對應(yīng)的下標(biāo)
    public int getIndex(int value){
        for (int i = 0; i < size; i++) {
            if(data[i]==value){
                return i;
            }
        }
        return -1;
 
    }
//    查找數(shù)組下標(biāo)為index的元素
    public int getValue(int index) {
        if (index < 0 || index > size - 1) {
            System.out.println("輸入下標(biāo)不合理");
            return -1;
        }
 
        return data[index];
    }
//    根據(jù)索引刪除元素,注意將最后一個元素置為0
    public void removeIndex(int index){
        if(index<0||index>=size){
            System.err.println("輸入不合法!");
        }
        for (int i = index; i <size-1; i++) {
            data[i]=data[i+1];
        }
        size--;
        data[size]=0;
    }
//    刪除第一個元素值為value的元素
    public void removeValueOnce(int value){
        int a=getIndex(value);
      removeIndex(a);
 
        }
//        刪除所有元素值為value的元素
    public void removeValueAll(int value){
        for (int i = 0; i < size; i++) {
           while(i!=size||data[i]==value)
               removeIndex(i);
 
        }
 
    }
//    根據(jù)索引修改元素
    public void recompose(int index,int newValue){
        if(index<0||index>=size){
            System.err.println("輸入不合法!");
        }
 
        data[index]=newValue;
    }
    }

鏈表

定義:

邏輯上連續(xù),物理上非連續(xù)存儲。

鏈表由一個個節(jié)點組成,每個節(jié)點存儲該節(jié)點處的元素值val 以及下一個節(jié)點的地址next,由地址next實現(xiàn)邏輯上連續(xù)

分類:

分類方式:

(1)單鏈表、雙鏈表

(2)帶虛擬頭節(jié)點、不帶虛擬頭節(jié)點

(3)循環(huán)鏈表、非循環(huán)鏈表

按不同分類方式組合有8種:

非循環(huán)四種:

(1)不帶虛擬頭節(jié)點的單向鏈表(非循環(huán))

(2)帶虛擬頭節(jié)點的單向鏈表(非循環(huán))

(3)不帶虛擬頭節(jié)點的雙向鏈表(非循環(huán))

(4)帶虛擬頭節(jié)點的雙向鏈表(非循環(huán))

循環(huán)四種:

(5)不帶虛擬頭節(jié)點的單向鏈表(循環(huán))

(6)帶虛擬頭節(jié)點的單向鏈表(循環(huán))

(7)不帶虛擬頭節(jié)點的雙向鏈表(循環(huán))

(8)帶虛擬頭節(jié)點的雙向鏈表(循環(huán))

其中:

(1)不帶虛擬頭節(jié)點的單向鏈表(非循環(huán)):結(jié)構(gòu)簡單,一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu),如哈希桶、圖的鄰接表等等。這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多

(7)不帶虛擬頭節(jié)點的雙向鏈表(循環(huán)):在Java的集合框架庫中LinkedList底層實現(xiàn)就是無頭雙向循環(huán)鏈表

實現(xiàn)方法:

增、刪、查、改     和順序表實現(xiàn)方法基本一樣;

唯一注意:帶虛擬頭節(jié)點與不帶虛擬頭節(jié)點相比,帶虛擬頭節(jié)點避免了考慮頭節(jié)點為空的特殊情況

代碼實現(xiàn):

(1)不帶虛擬頭節(jié)點的單鏈表:

class Node {
//    val表示存儲的數(shù)值,next表示下一個節(jié)點的地址
    int val;
    Node next;
 
    //    構(gòu)造方法
    public Node(int val) {
        this.val = val;
    }
}
 
public class SingleList {
    //    size表示節(jié)點個數(shù)
//    head表示頭節(jié)點
    private int size;
    private Node head;
 
    //定義toString方法以輸出鏈表內(nèi)容
    public String toString() {
        String str = "";
        Node node = head;
        while (node != null) {
            str += node.val;
            str += "->";
            node = node.next;
        }
        str += null;
        return str;
    }
 
    //將判斷輸入的索引是否合法抽象為方法islegal
    public boolean islegal(int index) {
        if (index < 0 || index > size) {
            return false;
        } else {
            return true;
        }
    }
 
    //    頭插法
    public void addHead(int value) {
        Node node = new Node(value);
        if (head == null) {
            head = node;
 
        } else {
            node.next = head;
            head = node;
        }
        size++;
    }
 
    //    中間任意位置插入
    public void addIndex(int index, int val) {
        if (!islegal(index)) {
            System.out.println("輸入數(shù)據(jù)不合法!");
            return;
        }
        if (index == 0) {
            addHead(val);
            return;
        }
        Node node = new Node(val);
        Node pre = head;
 
        for (int i = 0; i < index - 1; i++) {
            pre = pre.next;
        }
        node.next = pre.next;
        pre.next = node;
        size++;
        return;
    }
 
    //    尾插法
    public void addLast(int val) {
        if (head == null) {
            addHead(val);
        } else {
            addIndex(size, val);
        }
    }
 
    //    刪除指定索引位置的元素
    public void removeIndex(int index) {
 
        if (islegal(index)) {
            if (index == 0) {
                Node temp = head;
                head = head.next;
                temp.next = null;
                size--;
                return;
            } else {
 
                Node pre = head;
                for (int i = 0; i < index - 1; i++) {
                    pre = pre.next;
                }
                Node cur = pre.next;
                pre.next = cur.next;
                cur.next = null;
 
                size--;
            }
 
        } else {
            System.out.println("輸入數(shù)據(jù)不合法!");
        }
    }
 
    //    根據(jù)元素值刪除元素,且只刪除第一次出現(xiàn)的該元素
    public void removeValueOnce(int val) {
        if (head.next != null && head.val == val) {
            removeIndex(0);
        } else {
            Node pre = head;
            while (pre.next != null) {
                if (pre.next.val == val) {
                    pre.next = pre.next.next;
                    pre.next.next = null;
                    size--;
                    return;
 
                }
                pre = pre.next;
            }
        }
    }
 
    //    根據(jù)元素值刪除元素,且刪除所有該元素
    public void removeValueAll(int val) {
        while (head.next != null && head.val == val) {
            Node temp = head;
            head = head.next;
            temp = null;
            size--;
        }
        if (head == null) {
            return;
        } else {
            Node pre = head;
            while (pre.next != null) {
                if (pre.next.val == val) {
                    pre.next = pre.next.next;
                    size--;
                    return;
 
                } else {
                    pre = pre.next;
                }
            }
        }
    }
 
    //       根據(jù)元素值刪除元素,且刪除所有該元素并返回頭節(jié)點(帶虛假節(jié)點)
    public Node removeValueAllWithDummy(int val) {
        Node dummyHead = new Node(-1);
        dummyHead.next = head;
        Node pre = dummyHead;
        while (pre.next != null) {
            if (pre.next.val == val) {
                Node cur = pre.next;
                pre.next = cur.next;
                cur.next = null;
                size--;
            } else {
                pre = pre.next;
            }
        }
        return dummyHead.next;
 
    }
 
    //    根據(jù)索引查元素值
    public int get(int index) {
        if (islegal(index)) {
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.val;
        } else {
            System.out.println("輸入數(shù)據(jù)不合法!");
            return -1;
        }
    }
 
    //    能否查到給定的某元素值(自己寫的,好像很復(fù)雜)
    public boolean contains(int val) {
        boolean a = false;
        if (head == null) {
            System.out.println("該鏈表為空!");
            return false;
        } else {
            Node node = head;
 
            for (int i = 0; i < size; i++) {
                if (node.val == val) {
                    a = true;
                }
                node = node.next;
            }
        }
        return a;
    }
 
    //    能否查到給定的某元素值,老師寫的方法
    public boolean contains2(int val) {
        for (Node temp = head; temp != null; temp = temp.next) {
            if (temp.val == val) {
                return true;
            }
        }
        return false;
    }
 
    //    根據(jù)索引修改元素值
    public void set(int index, int newValue) {
        if (islegal(index)) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            node.val = newValue;
            return;
        }
        System.out.println("輸入數(shù)據(jù)不合法!");
    }
}

(2)帶虛擬頭節(jié)點的單鏈表

以在指定索引位置插入元素為例,理解虛擬頭節(jié)點的作用即可

public class SingleListWithDummyHead {
    Node dummyNode=new Node(-1);
    int size;
//    在指定位置插入元素,因為有虛擬頭節(jié)點故不用考慮index=0的情況,全部為在中間位置插入的情況
    public void addIndex(int index,int value){
//        先判斷index是否合法
        if(index<0||index>size){
            System.out.println("illegal");
            return;
        }
        Node a=new Node(value);
        Node pre=dummyNode;
        for(int i=0;i<index;i++){
            pre=pre.next;
        }
        a.next=pre.next;
        pre.next=a;
        size++;
    }
}

(3)帶虛擬頭節(jié)點的雙鏈表

public class DoubleLinkedList {
    private int size;
    private Node dummyHead = new Node(-1);
    private Node tail;
 
    //    定義toString方法用以方便輸出
    public String toString() {
        String s = "";
        Node node = dummyHead.next;
        while (node != null) {
            s = s + node.val;
            s = s + "->";
            node = node.next;
        }
        s += "null";
        return s;
    }
 
    //    判斷輸入的索引是否合法
    private boolean isRange(int index) {
        if (index < 0 || index >= size) {
            System.out.println("輸入不合法!");
            return false;
        } else
            return true;
    }
 
    //    頭插法
    public void addHead(int val) {
        Node a = new Node(val, dummyHead, dummyHead.next);
//鏈表為空
        if (dummyHead.next == null) {
            tail = a;
            dummyHead.next = a;
        }
//        否則鏈表不為空
        else {
            dummyHead.next.prev = a;
            dummyHead.next = a;
        }
        size++;
    }
 
    //    尾插法
    public void addTail(int val) {
        Node a = new Node(val, tail, null);
//        鏈表為空
        if (dummyHead.next == null) {
            dummyHead.next = a;
        }
//        鏈表不為空
        else {
            tail.next = a;
        }
        tail = a;
        size++;
    }
 
    //    中間位置插入
    public void addMiddle(int index, int val) {
//      判斷插入位置合理否
        if (index < 0 || index > size) {
            System.out.println("輸入不合法!");
        }
//        頭部插入
        else if (index == 0) {
            addHead(val);
        }
//        尾部插入
        else if (index == size) {
            addTail(val);
        }
//        中間任意位置插入
        else {
//先找到要插入位置的前一個元素,可另一個方法找該元素
            Node a = new Node(val, find(index), find(index).next);
            find(index).next.prev = a;
            find(index).next = a;
            size++;
        }
    }
 
    //    這里find的方法是找到index位置的前一個節(jié)點元素
    public Node find(int index) {
        Node f = dummyHead;
        for (int i = 0; i < index; i++) {
            f = f.next;
        }
        return f;
 
    }
 
    //    根據(jù)索引刪除指定位置的元素
    public void removeIndex(int index) {
        if (index < 0 || index >= size) {
            System.out.println("輸入不合法!");
            return;
        } else {
            find(index).next.next.prev = find(index);
            find(index).next = find(index).next.next;
            size--;
        }
    }
 
    //    刪除指定節(jié)點
    private void deleteNode(Node node) {
//        分治思想,先處理node與左邊節(jié)點,再處理node與右邊節(jié)點
        Node pre = node.prev;
        Node next = node.next;
//        處理左邊,因為有虛擬頭節(jié)點,故不用另討論為頭節(jié)點的情況
        pre.next = next;
        node.prev = null;
//       處理右邊
        if (next == null) {
            tail = pre;
        } else {
            next.prev = pre;
            node.next = null;
        }
        size--;
 
    }
 
    //    刪除指定元素值(只刪除第一次出現(xiàn)的)
    public void removeValueOnce(int val) {
        for (Node a = dummyHead.next; a != null; a = a.next) {
            if (a.val == val) {
                deleteNode(a);
                return;
            }
        }
        System.out.println("鏈表中無該元素故無法刪除");
 
    }
 
    public void removeValueAll(int val) {
        for (Node a = dummyHead.next; a != null; ) {
            if (a.val == val) {
                Node b = a.next;
                deleteNode(a);
                a = b;
            } else a = a.next;
        }
    }
 
    //    根據(jù)索引查找元素值
    public int get(int index) {
        if (isRange(index)) {
            return find(index).next.val;
        } else {
            return -1;
        }
    }
 
    //    查找是否存在某元素
    public boolean contains(int val) {
        Node a = dummyHead;
        while (a.next != null) {
            if (a.next.val == val) {
                return true;
            }
            a = a.next;
        }
        return false;
    }
 
    //    修改,將指定位置元素修改為另一值
    public void set(int index, int newValue) {
        if (isRange(index)) {
            find(index).next.val = newValue;
        }
 
    }
 
 
}
 
//節(jié)點類
class Node {
    int val;
    Node prev;
    Node next;
 
    public Node(int val) {
        this.val = val;
    }
 
    public Node(int val, Node prev, Node next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}
 

順序表 & 鏈表

順序表:

優(yōu)點:空間連續(xù)、支持隨機訪問

缺點:中間或前面部分的插入刪除時間復(fù)雜度O(N)

           增容的代價比較大。

鏈表:

優(yōu)點:任意位置插入刪除時間復(fù)雜度為O(1)

           沒有增容問題,插入一個開辟一個空間 

缺點:以節(jié)點為單位存儲,不支持隨機訪問

總結(jié)

到此這篇關(guān)于Java實現(xiàn)順序表和鏈表結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java順序表和鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java tomcat環(huán)境變量及idea配置解析

    Java tomcat環(huán)境變量及idea配置解析

    這篇文章主要介紹了Java tomcat環(huán)境變量及idea配置解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-12-12
  • 關(guān)于SpringBoot mysql數(shù)據(jù)庫時區(qū)問題

    關(guān)于SpringBoot mysql數(shù)據(jù)庫時區(qū)問題

    在后端開發(fā)過程中經(jīng)常會遇到幾個時區(qū)設(shè)置問題,今天分幾種情況給大家介紹SpringBoot mysql數(shù)據(jù)庫時區(qū)問題,感興趣的朋友跟隨小編一起看看吧
    2021-06-06
  • Spring5中的WebClient使用方法詳解

    Spring5中的WebClient使用方法詳解

    這篇文章主要給大家介紹了關(guān)于Spring5中WebClient使用方法的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用Spring5具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-11-11
  • SpringCloud負(fù)載均衡實現(xiàn)定向路由詳情

    SpringCloud負(fù)載均衡實現(xiàn)定向路由詳情

    這篇文章主要介紹了SpringCloud負(fù)載均衡實現(xiàn)定向路由詳情,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價值,需要的小伙伴可以參考一下
    2022-08-08
  • IDEA2021.2永久激活碼最新超詳細(xì)(激活到2099)

    IDEA2021.2永久激活碼最新超詳細(xì)(激活到2099)

    這篇文章主要介紹了IDEA2021.2永久激活碼,是idea2021版最新激活方法,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-09-09
  • IntelliJ IDEA像Eclipse一樣打開多個項目的圖文教程

    IntelliJ IDEA像Eclipse一樣打開多個項目的圖文教程

    這篇文章主要介紹了IntelliJ IDEA像Eclipse一樣打開多個項目的方法圖文教程講解,需要的朋友可以參考下
    2018-03-03
  • SpringBoot3整合mybatis-plus的實現(xiàn)

    SpringBoot3整合mybatis-plus的實現(xiàn)

    MyBatis-Plus是一個MyBatis的增強工具,在MyBatis的基礎(chǔ)上只做增強不做改變,本文主要介紹了Mybatis-Plus3.x的具體使用,具有一定的參考價值,感興趣的可以了解一下
    2023-10-10
  • Spring中的事務(wù)管理實例詳解

    Spring中的事務(wù)管理實例詳解

    這篇文章主要介紹了Spring中的事務(wù)管理,以實例形式詳細(xì)分析了事務(wù)的概念與特性以及事物管理的具體用法,需要的朋友可以參考下
    2014-11-11
  • SpringMVC異步處理的 5 種方式示例詳解

    SpringMVC異步處理的 5 種方式示例詳解

    這篇文章主要介紹了SpringMVC異步處理的 5 種方式,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-03-03
  • SpringBoot整合liquibase的實現(xiàn)方法

    SpringBoot整合liquibase的實現(xiàn)方法

    這篇文章主要介紹了SpringBoot整合liquibase的實現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-08-08

最新評論