QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4769|回复: 0
打印 上一主题 下一主题

【Java演示】什么是链表?数据结构

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-5-4 15:55 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    ) S! y+ y2 R8 ]' f9 q
    【Java演示】什么是链表?数据结构3 C( K* u  F$ z! {
    一、单向链表1 }9 K6 h& d* o. w& `, k8 Q

    1 {6 ~6 ~6 G  m1 @3 j; Z3 Z 1.png   @8 }0 w* @& E6 Y
    链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成。
    4 q! Q4 B6 Q0 i9 x* G5 {单向 链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next。
    / B% A& ?9 l% O: j链表的第1个节点被称为头节点,最后1个节点被称为尾节点,尾节点的next指针指向空。
    / Y0 g( q1 S  E; o+ j0 \2 e% b( g- u, ]
    什么叫随机存储呢?0 }6 N; ]* v$ k
    8 S$ u8 t* r0 }5 |7 u1 g
    如果说数组在内存中的存储方式是顺序存储,那么链表在内存中的存储方式则是随机存储 。
    / R- P. }9 D% K5 D) k! o: t+ F上一节我们讲解了数组的内存分配方式,数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式,链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。/ l+ [- Y, f( I9 F: e% C. c3 |
    3.png
    / r- C; b4 C& h5 o% m+ L5 G8 @: K! c9 s

    图中的箭头代表链表节点的next指针。

    链表的基本操作1. 查找节点

    在查找元素时,链表不像数组那样可以通过下标快速进行定位,只能从头节点开始向后一个一个节点逐一查找。

    4.png
    - m( P% q8 `+ Y2 ?) @) Y' i
    - f* [- c  a6 }+ M( i4 Q/ _$ s/**
    1 j( f* x1 r: d7 w% J     * 链表查找元素
    . n- D: A1 D1 Q; J# v( `     *
    ) r  i* q: i7 P5 `8 B     * @param index 查找的位置
    ' G" u# g+ f: L- j& A     * @return index位置的Node对象( J' D! c/ T" R9 R( V' n
         */+ Z% }8 l4 S: F0 Q$ B
        public Node get(int index) {
    , \: E* a: X9 w/ U: h) K% U0 }        if (index < 0 || index > size) {% w2 \, K/ G: I2 U$ M6 L" f
                throw new IndexOutOfBoundsException("超出链表的节点的范围!");
    6 Q2 K; s* C, t        }
    * d0 Z2 y2 s4 ]5 ^& q2 _% A8 F  ^        Node temp = head;) L  e+ p  b' K) @3 ?: E  ^; ]
            for (int i = 0; i < index; i++) {
    6 j6 J- H: p/ U' a            temp = temp.next;
    1 z$ j# z0 g" s5 j+ x7 e( S/ P$ E        }/ k% v0 O, z: i7 ~" v0 ]" B
            return temp;* B1 t" z; ~3 \* h2 |4 \
        }
      t2 q3 q, ^" ?
    8 O1 ?% P) {! H9 ]- ]2 b+ @# {

    链表中的数据只能按顺序进行访问,最坏的时间复杂度是O(n)

    2. 更新节点 5.png
    4 B/ ~: q4 _4 Z9 v3 W
    * e+ c( R8 s* ~# S) A# [+ X如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据替换成新数据即可。, T4 M2 z- W2 E* U2 H) p+ F- _
    如果不考虑查找元素的过程,只考虑纯粹的更新节点操作,时间复杂度是O(1)
    ( l" D6 D0 y& C9 R8 w/**
    4 D3 t6 Q" a7 {/ E* N     * 更新节点 将列表中指定位置的节点的data替换为指定的data。- X: x# F) U; b- T) o" a
         *1 q# u% t* q+ s
         * @param index 需要更新的节点的位置4 k$ {  `7 o9 y4 b: w# f
         * @param data  新data8 n6 R1 E$ b' E2 p& P/ h
         * @return 旧data0 p) [  \- D& M1 n7 i
         */
    $ M+ y0 K! \/ P# ~" t# H    public int set(int index, int data) {& m, v3 I" P, O- ~+ \; R
            Node x = get(index);
      r7 s/ n4 e0 V6 t2 n1 X4 W$ w        int oldVal = x.data;
    0 g- {- U# _  A+ L: W        x.data = data;, b1 M# ~0 F1 w5 g# G
            return oldVal;
    0 Y+ A( d, X2 v* N3 ~6 L    }
    5 r1 c' q& c6 B  O9 b8 Y, a+ s* \& C8 p3 z2 ?2 P
    3. 插入节点

    只要内存空间允许,能够插入链表的元素是无穷无尽的,不需要像数组那样考虑扩容的问题。

    与数组类似,链表插入节点时,同样分为3种情况。

    • 尾部插入
    • 头部插入
    • 中间插入
      : i% n* h1 @' F
    3.1. 尾部插入

    尾部插入,是最简单的情况,把最后一个节点的next指针指向新插入的节点即可。

    + ?/ q4 _& a! i( `& a' `
    6.png
    : d9 K' t$ E0 l- J9 x. I3.2. 头部插入

    头部插入,可以分成两个步骤。

    • 第1步,把新节点的next指针指向原先的头节点。
    • 第2步,把新节点变为链表的头节点。% ?, q# x6 z9 Z! G
    7.png * A& a- [4 ^) A% y+ o% x& f2 o/ v) q

    7 r( |3 \1 l% `2 h# e5 L  ]3.3. 中间插入

    中间插入,同样分为两个步骤。

    • 第1步,新节点的next指针,指向插入位置的节点。
    • 第2步,插入位置前置节点的next指针,指向新节点。
      ) l' G4 O" Z, ^
    8.png
    * n" ~3 Y' D5 n: P+ i6 o) F
    & w- W# H& X& P/ g: G三钟情况的代码合到一起
    ! h1 Y4 p0 h2 |0 u* ~7 Y$ T; v( x& j" A& i/ p
    /**
    / ^1 {4 b! H% |1 T2 D; {. q     * 链表插入元素/ n1 ^" y/ o# F  j
         *+ K, i' C, K; {9 ~# N1 |9 B: q; M
         * @param index 插入位置8 n" e1 c8 G8 g0 X6 n/ J0 `9 G' H
         * @param data  插入元素 被插入的链表节点的数据
    ( j3 r; y+ c3 F. |. {+ b     */0 x# R& g1 I. \& m. K2 h
        public void insert(int index, int data) {
    2 t: R. G% W+ i  d, s* {" W        if (index < 0 || index > size) {
    7 z% z' @' Z! T& q; I            throw new IndexOutOfBoundsException("超出链表节点范围!");6 d" R6 t2 ^/ o5 f3 u
            }# {# R" L' F: k  B0 u: a6 ]
            Node insertedNode = new Node(data);' g" i0 Y5 B- T# f. [
            if (size == 0) {( y; {9 h8 V6 h/ e% K0 Y
                //空链表! k. g# d9 r4 K- k- ^' K8 E
                head = insertedNode;
    : T" Z% F9 U( K            last = insertedNode;
    - p: o2 k: n5 e0 g        } else if (index == 0) {* \$ I) C3 y$ o. h+ b& X+ }0 A
                //插入头部
    ; o4 f4 ~' \: Y7 ^5 k            insertedNode.next = head;
    . M+ u9 {* _# r            head = insertedNode;
    , T& K; d2 a3 Q# t' z  |        } else if (size == index) {
    $ h/ j  l( E/ g: I7 [            //插入尾部+ C  D3 q8 g( [1 t% u+ Y
                last.next = insertedNode;
    4 y' O7 e0 x9 h# y9 W            last = insertedNode;% r! j! E5 z1 X% ^7 X6 x1 v! ]) g( N9 O
            } else {4 d$ b- E# I+ Y- R( I
                //插入中间
    ! R3 j" U0 @8 u5 L4 p. z            Node prvNode = get(index - 1);
    8 J, H4 ?2 e9 D            insertedNode.next = prvNode.next;# Q" E, ^" b+ w1 P9 y
                prvNode.next = insertedNode;
    6 y8 ^# o9 y. c+ O        }" f2 n! p2 x  X6 r( P. {7 Q
            size++;
    , ]4 f! q' s( P2 ^' M# W    }# W* g2 p' h2 ^: ?' ]: S- j# ]
    0 K9 i, {" Y! q$ F$ y7 x$ i
    /**
    : o  p$ O6 ~" t1 n1 r! h& r3 l' e     * 链表插入元素% F2 ~" [, k) W1 b& u5 ^* p
         *+ Y/ b& j$ y/ w) \# S
         * @param index 插入位置7 z% _, g* P/ T1 ^0 M0 X
         * @param data  插入元素 被插入的链表节点的数据" ~, S' q3 R8 ?8 b9 ~
         */
    0 {4 ]0 D7 G. G/ ~* \    public void insert(int index, int data) {1 w2 g# F8 O8 q4 S6 `2 S4 a& q
            if (index < 0 || index > size) {% k# F% M4 Z0 V* {
                throw new IndexOutOfBoundsException("超出链表节点范围!");7 L( g4 k1 S: g- r$ J0 p6 J1 p
            }
    7 E" x! S) G+ F0 N& k2 x        Node insertedNode = new Node(data);, z0 F8 b  o3 j+ i) J
            if (size == 0) {
    3 q; i+ z0 Q- z* N# S( w+ L3 Z            //空链表
    0 T( X! A. e& `' ^            head = insertedNode;
    4 S, M& I# T2 U1 U; |            last = insertedNode;
    & |" ^# y% R# |/ J. m6 e$ H6 ~4 m        } else if (index == 0) {: E8 y1 M) I9 {+ s6 q9 L9 d
                //插入头部0 R$ X% s3 s# G
                insertedNode.next = head;2 H0 s8 D5 F" ^7 U0 ^. X- t
                head = insertedNode;2 [" f  c, I( o& x7 i/ G' q, n
            } else if (size == index) {
    5 {7 u% i3 o" }1 r( z            //插入尾部- [7 z( j$ h+ V: d0 b2 G3 V6 c
                last.next = insertedNode;
    % V; D4 j$ @  q! m0 y# m" E$ }  d  Y            last = insertedNode;
    8 i6 {$ t5 C) U8 q- o; b* `- B( w        } else {: U. g# ?' t  b7 O) x
                //插入中间& f" q. |3 W0 x; x
                Node prvNode = get(index - 1);- x* W- J( _5 d: q/ s
                insertedNode.next = prvNode.next;
    : b% Q4 w; p6 Q: @8 q* c& {            prvNode.next = insertedNode;
    * z9 c0 O2 ]5 _2 m2 B- ]/ b( J        }
    " s/ G/ j0 s) B6 ?        size++;
    1 \* o$ y0 T3 H$ `- H- F: ~    }
    , ?5 ^1 R9 g$ W* Z+ ?" I  |5 Z4. 删除元素

    链表的删除操作同样分为3种情况。

    • 尾部删除
    • 头部删除
    • 中间删除
      , C7 J: U0 _, p5 ?1 X6 a/ s
    4.1. 尾部删除

    尾部删除,是最简单的情况,把倒数第2个节点的next指针指向空即  \1 D  y$ \" m+ @
    可。

    9.png
    $ f' [  {9 \( m! K4 a( x2 T: z
    " g/ V" n* w- O  _  ~4.1. 头部删除

    头部删除,也很简单,把链表的头节点设为原先头节点的next指针即可。

    10.png , V! d3 x; I  Y' V7 e2 Q
    * e; S& d' r" P7 j0 p
    4.1. 中间删除

    中间删除,同样很简单,把要删除节点的前置节点的next指针,指向要
    1 e4 N8 ?6 q$ m/ N1 X# o% L删除元素的下一个节点即可。

    11.png
    8 S8 r( ]  ?& s: G$ b. g6 p
    0 l  o$ v1 c! X' d; Y' I. N$ [
    , G/ w* |) M$ S4 C) D: I$ m, M这里需要注意的是,许多高级语言,如Java,拥有自动化的垃圾回收机制,所以我们不用刻意去释放被删除的节点,只要没有外部引用指向它们,被删除的节点会被自动回收。" w4 H! j5 b( `* d
    如果不考虑插入、删除操作之前查找元素的过程,只考虑纯粹的插入和删除操作,时间复杂度都是O(1)
    # E- M3 E' v' j+ @" q/**
    ' A0 W' S5 X( {" F! E+ b4 A     * 链表删除元素
    : `+ ~" J9 `1 m" S) e) @     *
      v+ U3 {8 c" r+ w$ F6 Q     * @param index 删除的位置
    ' `* A# ~4 [1 A  ]     * @return 被删除的节点
    % T0 G6 O$ g! m' b2 @# ~- g     */1 p4 b1 K  A* A) B1 U
        public Node remove(int index) {
    8 x9 b0 M/ Z7 n/ ^# W        if (index < 0 || index > size) {
    2 ?4 K4 U( D$ u! H            throw new IndexOutOfBoundsException("超出链表节点范围");
    3 a7 ^* y' k2 J0 X        }
    + h$ A$ ?7 Z3 E( y" u        Node removeNode;7 c' v. q; W, i* z8 x3 {7 i, o
            if (index == 0) {
    0 e, h# x+ ^  u& P( Z1 m            if (size == 0) {
    * m" Q5 H$ E  _0 U                throw new NullPointerException("当前链表为空,不可以进行删除操作");
    # B% t, G0 D1 g# e6 B# _            }( U! g! l/ u; d( C8 h5 F# h, Z
                //删除头节点# A4 x# r8 \5 X7 H
                removeNode = head;- {, x8 ]  u' L% n
                head = head.next;
    : }6 Y3 D2 Y2 H        } else if (index == size - 1) {" x4 q# r/ b8 d" G6 a
                //删除尾节点9 Y1 h) I+ T* ?$ Q9 H- g' \
                Node preNode = get(index - 1);/ c; ?2 [9 ^& q5 J! B3 w, Y# |: S3 k
                removeNode = preNode.next;6 q0 r, @5 ^( o4 J
                preNode.next = null;7 A% n& e) o# n: {* u+ N8 B
                last = preNode;6 `" ^) V, s2 A3 C" f
            } else {
    & d: n0 x' I% F! p  v1 U            //删除中间节点0 L6 m! L# g2 s. V$ H/ J/ D6 H" W
                Node prevNode = get(index - 1);' C5 @3 C6 U+ |/ g* O
                removeNode = prevNode.next;
    , ~4 \* H- p# y            prevNode.next = prevNode.next.next;7 V7 m7 m; d: `, w1 B% s( Q/ ~
            }1 ]" ^# M) w5 T( K6 v
            size--;
    4 v% |; E) N1 |9 L2 k        return removeNode;
    : \7 A7 A6 c( ~$ B' c/ @    }) S( \, Q: x) T; w5 N5 k; E
    Java实现链表的完整代码package chapter2.part2;) r8 o: w, R8 g, Z( C/ A2 @
    " n2 t% K- D; B+ k2 m9 _3 s
    /**
    ) v3 E# f% j5 `. L2 F( {6 B' r6 g. z * Created by IntelliJ IDEA.
    ; V6 E7 M4 Y! w( d *! e* |3 p. c2 ]1 r& w& B0 K
    * @Author: 张志浩  Zhang Zhihao
    5 O, A' V% m% j5 d * @Email: 3382885270@qq.com+ z8 Q( j% j' a& g. @, f
    * @Date: 2020/5/35 {" E+ g$ z$ [4 \' R$ h
    * @Time: 13:39# r/ u2 g, j1 ?, b
    * @Version: 1.0
      `) d& @& y6 S; o */5 ?$ h0 }" Z, x% M: |, T" F& \5 X
    public class MyLinkedList2 {. N1 }7 k* n! W
        private Node head; //头节点- G1 q- C" L* W7 ?, k
        private Node last; //尾节点
    # x) x8 g7 q: R% ^9 N6 F. q5 F    private int size; //链表实际长度) t8 P: c4 U) ]8 M

    1 q2 t- N- S5 H    public static void main(String[] args) {' Z5 G& h6 }7 ~, W4 c+ r
            MyLinkedList2 myLinkedList = new MyLinkedList2();. [3 Z7 U" {+ e; P
    //        myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空,不可以进行删除操作' z# j) Y: E5 F7 D
    //        myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围
    . C+ G3 C, \9 ~) ^        myLinkedList.insert(0, 3);8 Q7 p' c0 }3 q
            myLinkedList.insert(1, 7);, w# t6 [6 x8 k: p( Q" v" o
            myLinkedList.insert(2, 9);- N6 H. y& a" e. H" u, [, m
            myLinkedList.insert(3, 5);1 m$ M. Z. z/ S  G" Q- m! S2 |
            myLinkedList.insert(1, 6);
    / {& H- T/ h, t        myLinkedList.remove(0);) m# t! O& D* v% g
            myLinkedList.set(0, 23);6 g( C5 P' _2 k% f8 g; {
            myLinkedList.output();
    ( r5 ?0 w1 Q) \! e6 z* c# j  t3 o" J    }6 ]; T( ]* e! t: ?5 @; D5 X, j

    $ c* I  v& e2 e    /*** P3 V2 S- e: D6 |1 e. L, b
         * 链表插入元素8 f" P" }$ M: ]; J5 K
         *9 T7 K, V5 x6 T* {2 ?0 M& `+ I
         * @param index 插入位置
    ; c& O1 k# B9 {     * @param data  插入元素 被插入的链表节点的数据1 H) V. A1 A: X2 `% t' x* @
         */' [. N% x. W$ |
        public void insert(int index, int data) {5 \+ G! }# Z: {
            if (index < 0 || index > size) {
    ) Q, m/ c$ D& a( X            throw new IndexOutOfBoundsException("超出链表节点范围!");5 G6 P( O$ w: [# Y4 M
            }! s  `( D: v7 h5 `' M# q
            Node insertedNode = new Node(data);+ ?4 Q( |" [& P
            if (size == 0) {
    : a+ a  S" ?7 `6 [            //空链表/ g( i( _6 V. M0 z1 P5 p0 V) }
                head = insertedNode;
    ( x4 J0 Y4 B) c& p6 ?" t            last = insertedNode;
    4 v8 O. I0 \( ~8 n$ u3 g& B$ f        } else if (index == 0) {
    1 f6 x- Z; f, W; }) |$ R3 @1 `            //插入头部  q0 i6 C3 M' t+ a
                insertedNode.next = head;% h7 @% i5 ^( e4 L5 R7 p
                head = insertedNode;
    4 |0 [! o3 e( V        } else if (size == index) {8 p' l/ }1 v; W; d
                //插入尾部
    6 N7 c/ i% b- A! }$ L! L5 e            last.next = insertedNode;
    + B" ]* l1 Q& c: X# @& a% c            last = insertedNode;" t( ?; L5 ^4 a# h% y& [
            } else {+ j+ r$ P6 e% v; j
                //插入中间
    ) J; S7 k; \6 S' A- r            Node prvNode = get(index - 1);, J. ]! S% a. o; \7 L9 V* q& ~
                insertedNode.next = prvNode.next;
    9 Z% z) h- V  B. h            prvNode.next = insertedNode;: U" W9 R  ]0 ?9 A3 S( d
            }6 b4 t$ x. X6 v2 y/ `% X2 Y
            size++;8 T  K5 t- U6 J1 \& Q4 z% s  X
        }4 F+ T0 ]' |; A
    , g5 @! k& ~+ @0 C4 A$ X$ A# T
        /**
    + e7 ~# Y) F0 W: ~) Y: w     * 链表删除元素' @9 j( r4 ~, @& l( v
         *2 E( l* P# C& p) f8 n& e& i/ N; u
         * @param index 删除的位置4 q. b: L. N0 B
         * @return 被删除的节点
    3 e9 y+ X5 |: \% W/ ]% V     */
    9 Y& L% Y, h3 t, F2 c& b    public Node remove(int index) {
    3 K; {  X, Y+ m( ^/ f        if (index < 0 || index > size) {1 b3 a0 ~/ [" ^. c0 P% r$ G
                throw new IndexOutOfBoundsException("超出链表节点范围");; T4 }* E9 ?7 x/ I- k# M  Z
            }, U. T6 y0 E' o. s- W# h# b
            Node removeNode;% S' d- S% f& X6 @0 ^  }$ z
            if (index == 0) {6 b1 K% r# P. f* W* f+ c- p
                if (size == 0) {1 L; |7 o7 _" I. y6 g$ U
                    throw new NullPointerException("当前链表为空,不可以进行删除操作");
    8 M2 w5 w5 n/ P  \  u) l% _            }
    ; e0 b1 t* x4 I* t9 V            //删除头节点
    0 {9 M+ `8 h$ V4 O9 H            removeNode = head;
    % F# h" M# |$ Q            head = head.next;
    9 |$ j7 b6 B4 g( C5 ~        } else if (index == size - 1) {
      z7 U  x, g0 w5 I+ U            //删除尾节点
    " @3 C$ Q* e! U+ @            Node preNode = get(index - 1);* L  g: i/ ^  ]' y
                removeNode = preNode.next;% \, p0 b* y, f: U
                preNode.next = null;
    - E, Z4 C2 J# q; e6 m            last = preNode;
    # k2 g2 w/ Z( _( ?        } else {, M3 ?; G8 G! O
                //删除中间节点
    ! g" `) p, v( J: O  u0 C            Node prevNode = get(index - 1);, X" Y- _2 K0 V+ a6 E% I- }: w1 I
                removeNode = prevNode.next;" f4 P5 T6 ~9 S: `7 K* L; f
                prevNode.next = prevNode.next.next;- X5 \+ q0 [2 x0 V" m* [
            }
    1 h7 z9 A% I0 \( g/ s        size--;
    & `7 E. Z$ ~+ V9 X        return removeNode;
    3 i2 U6 w5 Q" a- W/ z, P8 m" L    }/ C) g+ Z8 b% n3 d
    # N- Q( D; a$ {1 j
        /**
    & J9 @# f  c+ Y9 Z     * 更新节点 将列表中指定位置的节点的data替换为指定的data。" d9 W+ A4 S( p9 x3 J+ C& j
         *
    * [4 P$ `9 n8 \6 M! q1 d. F, u     * @param index 需要更新的节点的位置2 t5 }/ Y' x% \( a6 p1 ]
         * @param data  新data
    - p. J. s" p8 B, O9 W8 X1 b1 i7 n     * @return 旧data
    ! Q& R2 f, Q6 R0 a     */: f; v  ~( O5 E: G
        public int set(int index, int data) {9 [( d6 q0 K, h$ x* ]' h7 e8 P2 n
            Node x = get(index);
    ) ?6 J! e, v0 @* E        int oldVal = x.data;# f. T' N& C, f% q1 b' o# _, x
            x.data = data;
    2 X+ y3 k/ y) J! ?3 }4 V- m2 p, g        return oldVal;, Z5 v0 ]9 [4 e3 X. k9 a, t
        }* V! l; v. E+ m4 H! F& G
    0 [8 @, a6 I& O7 I) T$ s
        /**) X- u& F# z9 @; A8 k
         * 链表查找元素
    2 S. Z! ~8 X) d2 z# T     *  n, z, h% u# I1 K
         * @param index 查找的位置
    ( y: h8 t7 y$ X& ?% b" E     * @return index位置的Node对象& |" {8 i" m7 T- D  s
         */
    + S$ V; x9 o- y1 q  l8 l    public Node get(int index) {0 \+ r0 C5 f" o
            if (index < 0 || index > size) {3 `: a; E7 w# T- p+ Y* m- l
                throw new IndexOutOfBoundsException("超出链表的节点的范围!");
    / M5 _* X, h; Q6 w$ v2 L. t8 S: }        }
    0 U0 J. o. G% i- z        Node temp = head;
    - J% j4 X0 y: L' k        for (int i = 0; i < index; i++) {4 f% y5 W" h. I
                temp = temp.next;
    " ]; z# Q2 ^' Z3 E        }8 t. x: M* m; [$ c- k1 s" r/ X
            return temp;
    % l1 S0 s8 _8 `    }, [( G. {: Z, `7 M

    9 Q# P% C- s) q, y2 [6 U! A# g    /**$ K/ e0 I3 f( P& b, X- H
         * 输出链表
    7 W6 }9 Q( @- R1 H$ B     */
    4 q! o+ G7 s3 t; y. w5 M    public void output() {
    $ b% f9 e, \: A. {        Node temp = head;
    ' q8 `: n; d- \/ U# f        while (temp != null) {7 E/ q3 [" J2 c
                System.out.print(temp.data + " ");: Q: W4 M5 ]; H
                temp = temp.next;) m3 T" a# T( Y, Q
            }' N! R3 k5 G- {( j7 I: U
        }
    ! l( @' x; _/ J1 A: O  y- T
    / u% k7 r& K1 V: h  i0 A4 f% P$ f    /**4 O% J8 A6 J8 P7 d1 H& Z4 q( f5 O
         * 链表节点3 \4 x4 N$ W8 W7 G( ]2 ~* i, D
         */2 M( R, H5 J- ~+ i% ~
        class Node {
    2 X7 p+ n- H% \& s2 @7 k" K        int data;( C" U! H& `2 ^8 |
            Node next;
    / [- ]0 C; X  P8 @# F6 `
    . A. }+ {  q- }# U- s* x7 D* `        Node(int data) {  C# a+ h1 k! {! |# ^1 O: n# f
                this.data = data;
    * @6 B# z/ Y& _+ g2 `9 ~# ~        }
    5 e/ D. L! u5 X' x! O    }
    0 Y: Y, j3 S$ t) C% b' E$ x. D* ?}
    ' c9 Y5 o) y3 y& Y; D  Y; `( B# \9 `7 j6 I: s
    ; H/ c( W# R* S, Z: u" D
    二、双向链表 12.png
    - [6 a2 e* S* Z- w双向链表比单向链表稍微复杂一些,它的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev 指针。
    7 W7 p6 K7 A4 Z0 @9 h+ \3 C* E  f, _
    3 m" S) c0 I2 n9 x% w! w/ l
    9 y2 s# \! h! W! @& `, y2 `  u! o* E+ g( V0 V
    ( m7 Q) A9 U7 G& L9 \4 S
    ————————————————
    7 N% E9 K( T& I6 r. U- F版权声明:本文为CSDN博主「爱做梦的鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。) s! D* M4 A! V, Z0 l, W% q
    原文链接:https://blog.csdn.net/weixin_43124279/article/details/105904468( C6 [% r3 z! q0 n3 U$ u; d0 ~; w

      O; A8 X5 y/ U8 L+ |; }! d# A/ m) e, l  p

    2.png (256.36 KB, 下载次数: 239)

    2.png

    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-7-28 19:22 , Processed in 0.495242 second(s), 53 queries .

    回顶部