java中單向鏈表和雙向鏈表是什么

小編給大家分享一下java中單向鏈表和雙向鏈表是什么，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、鏈表簡介

1、鏈表概念

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列節(jié)點(diǎn)組成，節(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成，節(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

2、基礎(chǔ)特點(diǎn)

內(nèi)存存儲(chǔ)

邏輯結(jié)構(gòu)

特點(diǎn)描述

• 物理存儲(chǔ)上是無序且不連續(xù)的；

• 鏈表是由多個(gè)節(jié)點(diǎn)以鏈?zhǔn)浇Y(jié)構(gòu)組成；

• 邏輯層面上看形成一個(gè)有序的鏈路結(jié)構(gòu)；

鏈表結(jié)構(gòu)解決數(shù)組存儲(chǔ)需要預(yù)先知道元素個(gè)數(shù)的缺陷，可以充分利用內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。

二、單向鏈表

1、基礎(chǔ)描述

單向鏈表是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，鏈表的遍歷要從頭部開始順序讀取；結(jié)點(diǎn)構(gòu)成，head指針指向第一個(gè)成為表頭結(jié)點(diǎn)，終止于最后一個(gè)指向NULL的指針。

2、基礎(chǔ)操作

添加數(shù)據(jù)

• 初始化head節(jié)點(diǎn)，作為鏈表的頭；

• 修改當(dāng)前末尾節(jié)點(diǎn)的next指針；

• 新添加的節(jié)點(diǎn)房子在鏈表末尾；

刪除數(shù)據(jù)

遍歷找到要?jiǎng)h除的節(jié)點(diǎn)，把刪除節(jié)點(diǎn)前個(gè)節(jié)點(diǎn)的指針指向該刪除節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)；

三、雙向鏈表

1、概念描述

雙向鏈表也叫雙鏈表，是鏈表的一種，鏈表的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很快速地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，鏈表結(jié)構(gòu)的使用多數(shù)都是構(gòu)造雙向循環(huán)鏈表。

2、基礎(chǔ)操作

添加數(shù)據(jù)

• 遍歷找到鏈表的最后一個(gè)節(jié)點(diǎn)；

• 修改當(dāng)前末尾節(jié)點(diǎn)的next指針；

• 新添加的節(jié)點(diǎn)房子在鏈表末尾；

• 添加最新尾節(jié)點(diǎn)的prev指針；

刪除數(shù)據(jù)

• 雙向鏈表，基于要?jiǎng)h除節(jié)點(diǎn)操作即可；

• 操作上圖中要?jiǎng)h除的Node2節(jié)點(diǎn)；

• Node2.prev.next = Node2.next;

• Node2.next.prev = Node2.prev;

通過上述流程的操作，就把鏈表中一個(gè)節(jié)點(diǎn)刪除，剩下節(jié)點(diǎn)再度連接成鏈?zhǔn)浇Y(jié)構(gòu)。

3、源碼分析

在Java的API中，LinkedList是典型的雙向鏈表結(jié)構(gòu)，下面基于LinkedList源碼看雙向鏈表的操作。

基礎(chǔ)案例

public class M01_Linked {
    public static void main(String[] args) {
        List<User> userList = new LinkedList<>() ;
        User removeUser = new User(200,"Second") ;
        // 添加元素
        userList.add(new User(100,"First")) ;
        userList.add(removeUser) ;
        userList.add(new User(300,"Third")) ;
        System.out.println("初始化："+userList);
        // 修改元素
        userList.get(0).setUserName("Zero");
        System.out.println("修改后："+userList);
        // 刪除元素
        userList.remove(removeUser) ;
        System.out.println("刪除后："+userList);
    }
}
class User {
    private Integer userId ;
    private String userName ;
    public User(Integer userId, String userName) {
        this.userId = userId;
        this.userName = userName;
    }
    @Override
    public String toString() {
        return "User{" +
                "userId=" + userId +
                ", userName='" + userName + '\'' +
                '}';
    }
    // 省略Get和Set方法
}

節(jié)點(diǎn)描述

節(jié)點(diǎn)三個(gè)核心描述：數(shù)據(jù)，next指針，prev指針。

private static class Node<E> {
    E item;         // 數(shù)據(jù)
    Node<E> next;   // 下個(gè)指針
    Node<E> prev;   // 上個(gè)指針
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

首位節(jié)點(diǎn)處理

基于LinkedList源碼，首尾節(jié)點(diǎn)方式，針對上圖雙鏈表的首位指針特點(diǎn)，這里源碼很好理解。

public class LinkedList {
    transient Node<E> first;
    transient Node<E> last;
    // 處理首節(jié)點(diǎn)
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
    }
    // 處理尾節(jié)點(diǎn)
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    }
}

添加節(jié)點(diǎn)

添加節(jié)點(diǎn)的方法直接調(diào)用linkLast方法，把新節(jié)點(diǎn)放到鏈表的尾部即可。

public boolean add(E e) {
    linkLast(e);
    return true;
}

刪除節(jié)點(diǎn)

第一步：遍歷對比，找到要?jiǎng)h除的節(jié)點(diǎn)；

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

第二步：移除節(jié)點(diǎn)，重新搭建鏈表結(jié)構(gòu)，并且把當(dāng)前鏈表的數(shù)據(jù)置為null，并返回被移除的節(jié)點(diǎn)；

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    return element;
}

如上就是對Java中LinkedList雙鏈表源碼的部分結(jié)構(gòu)分析，這種代碼看多了，總感覺自己寫的代碼不是Java。

四、環(huán)形鏈表

在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)，這樣就形成了環(huán)形鏈表：

環(huán)形鏈表鏈表的一種結(jié)構(gòu)，特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。

以上是“java中單向鏈表和雙向鏈表是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！