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

Java數(shù)據(jù)結(jié)構(gòu)之鏈表實(shí)現(xiàn)(單向、雙向鏈表及鏈表反轉(zhuǎn))

 更新時(shí)間:2021年06月02日 09:47:55   作者:放肆的青春゛つ  
這篇文章主要給大家介紹了關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之鏈表實(shí)現(xiàn)的相關(guān)資料,其中包括單向鏈表、雙向鏈表及鏈表反轉(zhuǎn)的實(shí)現(xiàn)代碼,需要的朋友可以參考下

前言

之前學(xué)習(xí)的順序表查詢非常快,時(shí)間復(fù)雜度為O(1),但是增刪改效率非常低,因?yàn)槊恳淮卧鰟h改都會(huì)元素的移動(dòng)??梢允褂昧硪环N存儲(chǔ)方式-鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)。鏈表由一序列的結(jié)點(diǎn)(鏈表中的每一個(gè)元素成為結(jié)點(diǎn))組成。

結(jié)點(diǎn)API設(shè)計(jì)

類名 Node
構(gòu)造方法 Node(T t,Node next) 創(chuàng)建Node對(duì)象
成員變量

T item:存儲(chǔ)數(shù)據(jù)

Node next :指向下一個(gè)結(jié)點(diǎn)

結(jié)點(diǎn)類

public class Node<T>{
    Node next;
    private T item;
 
    public Node(Node next, T item) {
        this.next = next;
        this.item = item;
    }
}

生成鏈表

public class TestNode {
    public static void main(String[] args) {
        // 生成結(jié)點(diǎn)
        Node<Integer> one = new Node<Integer>(null,12);
        Node<Integer> two = new Node<Integer>(null,16);
        Node<Integer> three = new Node<Integer>(null,11);
        Node<Integer> four = new Node<Integer>(null,10);
        //生成鏈表
        one.next = two;
        two.next = three;
        three.next =four;
    }
}

1、單鏈表

單向鏈表是鏈表的一種,它有多個(gè)結(jié)點(diǎn)組成,每個(gè)結(jié)點(diǎn)都由一個(gè)數(shù)據(jù)域一個(gè)指針組成,數(shù)據(jù)域用來存儲(chǔ)數(shù)據(jù),指針域用來指向其后結(jié)點(diǎn)。

鏈表的頭結(jié)點(diǎn)數(shù)據(jù)域不存儲(chǔ)數(shù)據(jù),指針域指向第一個(gè)真正存儲(chǔ)數(shù)據(jù)的結(jié)點(diǎn)。

單向鏈表API設(shè)計(jì)

類名 LinkList
構(gòu)造方法 LinkList() :創(chuàng)建LinkList對(duì)象
成員變量

private Node head;記錄首結(jié)點(diǎn)

private int N; 記錄鏈表的長度

成員內(nèi)部類 private class Node;結(jié)點(diǎn)類
成員方法
public void clear() 清空鏈表
public boolean isEmpty() 判斷鏈表是否為空,是返回true
public int length() 獲取鏈表中的元素個(gè)數(shù)
public T get(int i) 讀取并返回鏈表中的第i個(gè)元素的值

public void insert(T t)

往鏈表中插入一個(gè)元素
public void insert(T t,int i) 在鏈表的第i位置插入一個(gè)值為t的數(shù)據(jù)元素
public T remove(int i) 刪除并返回刪除鏈表中的第i個(gè)數(shù)據(jù)元素
public int indexof(T t) 返回鏈表中首次出現(xiàn)的指定的數(shù)據(jù)元素的序號(hào),如不存在,則返回-1

單向鏈表Java代碼實(shí)現(xiàn)

package com.ycy.Algorithm.LinkList;
 
 
import java.util.Iterator;
 
/**
 * 鏈表的head是不可以動(dòng)的
 * @param <T>
 */
public class LinkList<T> implements Iterable<T>{
 
    private Node head;//頭結(jié)點(diǎn),鏈表的head是不可以動(dòng)的
    private int N;//結(jié)點(diǎn)個(gè)數(shù)
    public LinkList() {
        this.head = new Node(null,null);
        N = 0;
    }
    /**
     * 結(jié)點(diǎn)內(nèi)部類
     */
    private class Node{
        //存儲(chǔ)數(shù)據(jù)
        T item;
        //下一個(gè)結(jié)點(diǎn)
        Node next;
        public Node(T item,Node next) {
            this.item = item;
            this.next = next;
        }
 
    }
    /**
     * 清空鏈表
     */
    public void clear(){
        head.item=null;
        head.next=null;// 頭節(jié)點(diǎn)next為null就是空鏈表
        this.N=0;
    }
    /**
     * 判斷鏈表是否為空
     */
    public boolean isEmpty(){
        return this.N==0;
    }
    /**
     * 獲取鏈表的長度
     */
    public int length(){
        return this.N;
    }
    /**
     * 讀取鏈表第i位置的元素值并返回
     */
    public T get(int i){
        //非法性檢查
        if(i<0 || i > this.N){
            throw new RuntimeException("位置不合法");
        }
        // n也是指向頭結(jié)點(diǎn)
        Node n = head;
        for(int index=0; index<i; index++){
            n = n.next;
        }
        return n.item;
    }
    /**
     * 往鏈表中插入數(shù)據(jù)t
     */
    public void insert(T t){
        // head不可以移動(dòng),不然就無法在找到鏈表
        // 定義一個(gè)臨時(shí)的Node也指向head的指針就可以通過移動(dòng)該指針就可以
        Node n = head;
        // 獲取尾節(jié)點(diǎn)
        while(true){
            // 當(dāng)剛好就一個(gè)節(jié)點(diǎn)時(shí)(頭節(jié)點(diǎn))
            if(n.next == null){
                break;
            }
            n = n.next;
        }
        //當(dāng)為空表時(shí),就可以插入
        Node node = new Node(t, null);
        n.next =node;
        this.N ++;
    }
 
    /**
     * 在第i位置上插入數(shù)據(jù)t
     */
    public void insert(T t,int i){
        // 非法性檢查
        if(i < 0 || i > this.N){
            throw  new RuntimeException("插入位置❌");
        }
        Node pre = head;
        for(int index=0;index <= i-1; index++){
            pre = pre.next;
        }
        Node current = pre.next;
        //先鏈接后面結(jié)點(diǎn)
        Node newNode = new Node(t,null);
        pre.next = newNode;
        newNode.next = current;
        this.N++;
    }
    /**
     * 移除并返回第i位置的元素值
     */
    public  T remove(int i){
        // 非法性檢查
        if(i < 0 || i >this.N){
            throw  new RuntimeException("刪除位置有誤");
        }
        Node n =head;
        for(int index=0;index <= i-1;index ++){
             n = n.next;
        }
        //要?jiǎng)h除的節(jié)點(diǎn)
        Node curr = n.next;
        n.next = curr.next;
        this.N--;//結(jié)點(diǎn)個(gè)數(shù)減一
        return curr.item;
    }
    //查找元素t在鏈表中第一次出現(xiàn)的位置
    public int indexof(T t){
        Node n = head;
        for(int i = 0; n.next != null;i++){
            n =n.next;
            if(n.item.equals(t)){
                return i;
            }
        }
        return -1;
    }
 
    @Override
    public Iterator iterator() {
        return new Iterator() {
            Node n =head;
            @Override
            public boolean hasNext() {
                return n.next !=null;
            }
            @Override
            public Object next() {
                //下移一個(gè)指針
                n = n.next;
                return n.item;
            }
        };
    }
}

 補(bǔ)充一點(diǎn)鏈表的賦值給新的鏈表后,兩個(gè)鏈表是會(huì)相會(huì)影響的,說白了就是把地址賦值給它了,他們操作是同一塊內(nèi)存的同一個(gè)對(duì)象。Node n = head;把head賦值給n,現(xiàn)在對(duì)n操作也是會(huì)影響head的

其中提供遍歷方式,實(shí)現(xiàn)Iterable接口。

測試代碼:

public class test {
    public static void main(String[] args) {
        LinkList<Integer>linkList = new LinkList<>();
        linkList.insert(1);
        linkList.insert(2);
        linkList.insert(4);
        linkList.insert(3);
        linkList.insert(1,2);
        for (Integer i : linkList) {
            System.out.print(i+" ");
        }
    }
}

運(yùn)行結(jié)果:

D:\Java\jdk-12.0.2\bin\java.exe "-javaagent:D:\IDEA\IntelliJ IDEA 2019.1\lib\idea_rt.jar=3542:D:\IDEA\IntelliJ IDEA 2019.1
1 2 1 4 3 

學(xué)習(xí)完鏈表還是需要加以練習(xí)的,可以在LeetCode上刷題加深理解。

2、雙向鏈表

頭插法:新增節(jié)點(diǎn)總是插在頭部

便于理解可以畫圖表示

頭插法:原圖,node是待插入的結(jié)點(diǎn).

插入后圖:

關(guān)鍵性代碼:

尾插法:新增節(jié)點(diǎn)總是插在尾部

原圖如下: 

 

插入結(jié)點(diǎn)后圖如下:

關(guān)鍵性代碼:

中間任意位置插入

插入之前的原圖: 

 

插入到鏈表中間位置:

關(guān)鍵性代碼:

代碼演示:

class MyLinkedList {
    Node head;//定義雙向鏈表的頭節(jié)點(diǎn)
    Node last;//定義雙向鏈表的尾節(jié)點(diǎn)
 
    //打印雙向鏈表
    public void disPlay() {
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
 
    //求雙向鏈表的長度(之后addIndex代碼會(huì)用到)
    public int size() {
        int count = 0;
        Node cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
 
    //頭插法
    public void addFirst(int data) {
        Node node = new Node(data);//定義一個(gè)用作插入的節(jié)點(diǎn)
        //1.假設(shè)雙向鏈表為空
        if (this.head == null) {
            this.head = node;
            this.last = node;
        } else {
            //2.雙向鏈表不為空的情況下
            //不懂請(qǐng)看上面的圖解,就很簡單了
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }
 
    //尾插法(與頭插法類似)
    public void addLast(int data) {
        //定義一個(gè)用作插入的節(jié)點(diǎn)
        Node node = new Node(data);
        //1.假設(shè)雙向鏈表為空
        if (this.head == null) {
            this.head = node;
            this.last = node;
        } else {
            //2.雙向鏈表不為空的情況下
            //不懂請(qǐng)看上面的圖解,就很簡單了
            last.next = node;
            node.prev = last;
            last = node;
        }
    }
 
    //在任意位置插入
    public void addIndex(int index, int data) {//形參index為插入元素位置,data為插入的數(shù)值
        //定義一個(gè)用作插入的節(jié)點(diǎn)
        Node node = new Node(data);
        Node cur = this.head;//定義一個(gè)cur用作遍歷雙向鏈表
        //1、判斷插入位置的合法性
        if (index < 0 || index > size()) {
            System.out.println("插入位置不合法!??!");
            return;
        }
        //2、假設(shè)插入位置為頭結(jié)點(diǎn)的情況下,即就是頭插法
        if (index == 0) {
            addFirst(data);//調(diào)用頭插法代碼
            return;
        }
        //3、假設(shè)插入位置為尾結(jié)點(diǎn)的情況下,即就是尾插法
        if (index == size()) {
            addLast(data);//調(diào)用尾插法代碼
            return;
        }
        //4、在中間任意位置的情況下
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        //不懂請(qǐng)看上面的圖解,就很簡單了
        //核心代碼
        node.next = cur;
        node.prev = cur.prev;
        cur.prev = node;
        node.prev.next = node;
    }
}
 
//雙向鏈表的節(jié)點(diǎn)結(jié)構(gòu)
class Node {
    int val;
    Node prev;
    Node next;
 
    Node(int val) {
        this.val = val;
    }
}

3、鏈表反轉(zhuǎn)

public void reverse(){
        if(N==0){
        //當(dāng)前是空鏈表,不需要反轉(zhuǎn)
            return;
        }
        reverse(head.next);
}
    /**
     * @param curr 當(dāng)前遍歷的結(jié)點(diǎn)
     * @return 反轉(zhuǎn)后當(dāng)前結(jié)點(diǎn)上一個(gè)結(jié)點(diǎn)
     */
public Node reverse(Node curr){
        //已經(jīng)到了最后一個(gè)元素
        if(curr.next==null){
        //反轉(zhuǎn)后,頭結(jié)點(diǎn)應(yīng)該指向原鏈表中的最后一個(gè)元素
          head.next=curr;
          return curr;
        }
       //當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
       Node pre=reverse(curr.next);
       pre.next=curr;
       //當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)設(shè)為null
       curr.next=null;
       //返回當(dāng)前結(jié)點(diǎn)
       return curr;
}

總結(jié)

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

相關(guān)文章

  • 詳解Java類型擦除機(jī)制

    詳解Java類型擦除機(jī)制

    Java泛型是JDK 5引入的一個(gè)特性,它允許我們定義類和接口的時(shí)候使用參數(shù)類型,泛型在集合框架中被廣泛使用。這篇文章主要介紹了Java類型擦除機(jī)制,需要的朋友可以參考下
    2019-07-07
  • 解決IDEA報(bào)錯(cuò)war?exploded?is?not?valid問題

    解決IDEA報(bào)錯(cuò)war?exploded?is?not?valid問題

    在使用IntelliJ?IDEA時(shí)遇到'[projectname]warexploded'無效的問題,可以通過清除項(xiàng)目列表、重新導(dǎo)入項(xiàng)目和配置新的Tomcat來解決,確保在Tomcat配置中,將ApplicationContext修改為僅包含一個(gè)'/',這一方法或許能幫助遇到相似問題的開發(fā)者
    2024-09-09
  • 利用@Value注解為bean的屬性賦值方法總結(jié)

    利用@Value注解為bean的屬性賦值方法總結(jié)

    這篇文章主要介紹了利用@Value注解為bean的屬性賦值方法總結(jié),文中有詳細(xì)的代碼示例,對(duì)學(xué)習(xí)@Value注解有一定的參考價(jià)值,需要的朋友可以參考下
    2023-05-05
  • Springboot+echarts實(shí)現(xiàn)可視化

    Springboot+echarts實(shí)現(xiàn)可視化

    這篇文章主要為大家詳細(xì)介紹了Springboot+echarts實(shí)現(xiàn)可視化,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-12-12
  • Java的Hibernate框架中集合類數(shù)據(jù)結(jié)構(gòu)的映射編寫教程

    Java的Hibernate框架中集合類數(shù)據(jù)結(jié)構(gòu)的映射編寫教程

    Hibernate可以將Java中幾個(gè)內(nèi)置的集合結(jié)構(gòu)映射為數(shù)據(jù)庫使用的關(guān)系模型,下面我們就來看一下Java的Hibernate框架中集合類數(shù)據(jù)結(jié)構(gòu)的映射編寫教程:
    2016-07-07
  • Mybatis-Plus打印sql日志兩種方式

    Mybatis-Plus打印sql日志兩種方式

    這篇文章主要給大家介紹了關(guān)于Mybatis-Plus打印sql日志兩種方式,Mybatis-plus是MyBatis增強(qiáng)工具包,用于簡化CRUD操作,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-07-07
  • 詳解Java匿名內(nèi)部類

    詳解Java匿名內(nèi)部類

    這篇文章介紹了Java匿名內(nèi)部類的實(shí)現(xiàn),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-12-12
  • Java實(shí)現(xiàn)多人聊天室的原理與源碼

    Java實(shí)現(xiàn)多人聊天室的原理與源碼

    這篇文章主要給大家介紹了關(guān)于Java實(shí)現(xiàn)多人聊天室的原理與源碼的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-04-04
  • 解決springboot項(xiàng)目啟動(dòng)報(bào)錯(cuò)Error creating bean with name dataSourceScriptDatabaseInitializer問題

    解決springboot項(xiàng)目啟動(dòng)報(bào)錯(cuò)Error creating bean with&nb

    這篇文章主要介紹了解決springboot項(xiàng)目啟動(dòng)報(bào)錯(cuò)Error creating bean with name dataSourceScriptDatabaseInitializer問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助
    2024-03-03
  • MyBatis一對(duì)一級(jí)聯(lián)更新問題小結(jié)

    MyBatis一對(duì)一級(jí)聯(lián)更新問題小結(jié)

    日常工作中經(jīng)常會(huì)涉及到一對(duì)一級(jí)聯(lián)更新的問題,本文主要介紹了MyBatis一對(duì)一級(jí)聯(lián)更新問題小結(jié),具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-01-01

最新評(píng)論