QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5137|回复: 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
    4 M6 X8 o! ]( d) G, B
    【Java演示】什么是链表?数据结构
    3 M+ U+ z0 @/ O* A( a一、单向链表
    6 R0 R/ w, w) C5 o: J$ C+ c2 i# Y$ Y7 s0 j3 n! G1 _
    1.png
    . g$ h0 u: |1 X! Y: y6 u" Y链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成。
    & c4 ^! E# `( B" p( E7 Q单向 链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next。6 q! i1 n. I9 ~8 C
    链表的第1个节点被称为头节点,最后1个节点被称为尾节点,尾节点的next指针指向空。
    # z* X: C0 P$ E: ^
    9 h; X: l3 h! b9 K. ~什么叫随机存储呢?
    7 h$ {, t1 C6 x
    / j4 [$ O1 M5 {. d9 \& L0 W如果说数组在内存中的存储方式是顺序存储,那么链表在内存中的存储方式则是随机存储 。
    ( z, S) W) U9 Q" M; M上一节我们讲解了数组的内存分配方式,数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式,链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。
    - t' _) w/ v# m1 ?; ^ 3.png , z7 v) `2 ]# o2 Y" k# x
    7 V: \% i5 W5 F" c( s

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

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

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

    4.png
    2 D& s, d  e0 t' k, x4 G; P$ p; W" |+ t! a
    /**, B* [- L4 w# F. T9 A
         * 链表查找元素# ~1 ]* s0 A: t( @
         *
      n0 p8 z" X' {9 J( ~$ V# h     * @param index 查找的位置$ V- k! X7 F( p2 O  k9 ]
         * @return index位置的Node对象8 ^$ b( ]+ @, r' x6 h6 }
         */
    3 F2 F; p# w3 N2 P9 N# q1 J    public Node get(int index) {# [8 I* \0 N: Z0 }/ ]% m
            if (index < 0 || index > size) {! ]/ w; y! S6 R& y
                throw new IndexOutOfBoundsException("超出链表的节点的范围!");
    0 M: |% S: A1 ?8 w: b        }9 v/ t/ G7 o2 n3 Z1 f
            Node temp = head;
    0 m; e$ v- ^4 ~* E; `        for (int i = 0; i < index; i++) {$ s. c+ C  c: O( O( w8 N$ A+ ^
                temp = temp.next;
    " `7 \% k' c$ l2 g; O        }
      ~5 @! S2 }* K9 E& o# s3 j        return temp;( K& Q) i* b5 N; v8 b# N3 K  L
        }
    0 R2 p, Q- z+ m5 U% b$ U1 Y9 \- W5 @

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

    2. 更新节点 5.png
    1 L7 \4 E: A* k7 c& y7 w, E* h- g* J; S" N6 N5 Q
    如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据替换成新数据即可。
      X: [/ D! R$ X6 v0 w' I如果不考虑查找元素的过程,只考虑纯粹的更新节点操作,时间复杂度是O(1)
      Z5 u: |$ v  }5 P) F9 f2 k2 ?  c/**0 B( B, X& @, U. L) `( u
         * 更新节点 将列表中指定位置的节点的data替换为指定的data。& P+ m9 G& X8 V  U: [. U& e* l2 n: b
         *
    9 j1 r1 z. X, ]     * @param index 需要更新的节点的位置
    ! M( {, i" I! M" f2 L$ ]- H6 p, `) @     * @param data  新data
    - p& |. T0 V2 p, f) Y     * @return 旧data' o4 r2 I! F. G. N
         */
    * R- X: ^' ^. |/ ^    public int set(int index, int data) {; U; V  G- G( N0 z2 c: C9 W0 H
            Node x = get(index);
    2 O1 @3 u/ m/ F  Y        int oldVal = x.data;
    8 a- b3 D4 [1 C$ P" _; N, c        x.data = data;" c/ E' ]3 a# x1 a; J5 l$ a7 O
            return oldVal;% d) A2 P' i/ m; a
        }- g/ q5 C2 A" a+ V4 |$ t
    6 o7 u4 o5 m) I1 v6 i4 i, g: W
    3. 插入节点

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

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

    • 尾部插入
    • 头部插入
    • 中间插入# J- s" ~$ e6 Y* p1 b. ?
    3.1. 尾部插入

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

    ( Y6 a# h7 X5 g$ l
    6.png . v+ G0 L5 P4 ]/ R
    3.2. 头部插入

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

    • 第1步,把新节点的next指针指向原先的头节点。
    • 第2步,把新节点变为链表的头节点。1 ]' p4 y0 f* \. w9 @/ |
    7.png " T7 W' j$ S* k: k( i# V% T
    ) r8 T: F( V, J/ R, \; N
    3.3. 中间插入

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

    • 第1步,新节点的next指针,指向插入位置的节点。
    • 第2步,插入位置前置节点的next指针,指向新节点。
      , \" g  E; `7 t8 T$ |
    8.png 8 v9 A6 L& d* H6 B

    1 V7 }" y* S- M2 S/ x' N6 _" Z三钟情况的代码合到一起
    9 i: n2 b: c# f+ Y% U) L9 `) N, h: @/ e$ R
    /**+ t& F4 |: Q" Q  u
         * 链表插入元素# T( X8 j7 Z3 u
         *( S: @) P. \) R" n4 i
         * @param index 插入位置
    . p1 C+ o$ e. B7 \8 {     * @param data  插入元素 被插入的链表节点的数据
    + h. N: {4 J- \5 }. n# V     */
    4 f- X8 r/ {/ r/ _$ J0 B    public void insert(int index, int data) {
    2 ]  u. B: k9 W' c3 G        if (index < 0 || index > size) {
    ; T& }! Y" O( J            throw new IndexOutOfBoundsException("超出链表节点范围!");
    0 |, D# R) S3 c# o1 L  Q, U        }2 R& _4 {+ s- e6 v# V; Q
            Node insertedNode = new Node(data);# k0 ]6 R9 N( J: f! a
            if (size == 0) {
    3 I$ _9 w8 p  u$ |1 L3 }& Y% a            //空链表7 g5 w: d' ~/ k0 }
                head = insertedNode;& c+ s! l0 a/ F
                last = insertedNode;- [5 f9 m& ?2 s6 L! B
            } else if (index == 0) {
    / \# C0 G: O/ z* w            //插入头部) o. b7 p/ K9 E+ U7 u
                insertedNode.next = head;+ `. [+ K" I# U5 x, m, W6 t! ]+ Y) f* i
                head = insertedNode;% F1 z" A. F8 ?- b5 l
            } else if (size == index) {
    6 l* ?  a' J4 \: W+ p+ r( S+ R            //插入尾部
    ' _) c& c6 p* B( v: S5 Z            last.next = insertedNode;  P) l1 _5 ^3 Y7 ^' |9 |# A: W
                last = insertedNode;
    # M) d- w6 \( V& f% r- A- y        } else {; |8 k1 P0 o9 P! W6 c
                //插入中间
    8 _! t. f$ u$ P3 j( ~            Node prvNode = get(index - 1);- W/ i) t6 w/ i! F0 r% i% Y
                insertedNode.next = prvNode.next;; W  u. L( Q# @/ N" H: w  i
                prvNode.next = insertedNode;
    8 b9 u" y- k3 n9 t        }4 C/ g7 `1 T5 [- Z* E
            size++;4 O& t/ X/ n) q2 }. R6 p' c
        }
    1 M5 |1 h7 \8 ~4 [3 m, o( Q& e7 A$ |7 v- D  P% r( g! I: f( U/ ]
    /**+ X! D! I0 \; O
         * 链表插入元素
    , m& o; U$ s5 E- z! z' W2 z3 ]     *
    4 }9 w# n/ P9 g7 {     * @param index 插入位置
    ; Z' U5 g- y1 [' J3 N: w     * @param data  插入元素 被插入的链表节点的数据+ J7 c% k$ i0 R# H" `1 q4 T+ _
         */. P9 D2 N$ N- k6 Z3 }
        public void insert(int index, int data) {
    4 V9 I- B0 s* R( y8 d5 U4 m6 J7 J        if (index < 0 || index > size) {
    $ n5 o! N1 f- v            throw new IndexOutOfBoundsException("超出链表节点范围!");2 n" d* ^( P& I
            }) c# n- w5 n+ b% y
            Node insertedNode = new Node(data);7 d1 I9 d3 [! w. `
            if (size == 0) {& Z2 K) k+ G& G- ^4 x" {, H: l( X
                //空链表
    4 d# @5 y8 U8 `4 z7 |8 ]4 l, J4 O            head = insertedNode;: m1 m; t9 A3 u9 z9 f& W8 y. O
                last = insertedNode;; Q+ e8 B5 P- I; G9 {3 B# `
            } else if (index == 0) {+ I8 s! N4 f* R& u* x
                //插入头部
    % M' h9 n; T+ z( ^* p            insertedNode.next = head;
    - G; Z( ^" z8 j; f, l8 U; t5 o            head = insertedNode;
    6 G& P, H  l# r; z        } else if (size == index) {6 |& q3 E4 F! z9 p0 U
                //插入尾部
    : @) {/ i. [" M) s1 d+ B) f            last.next = insertedNode;
    * A- x: J/ L3 y- ^( C            last = insertedNode;  E- V. Q; U* V/ v* ?8 e( T
            } else {
    2 M! P8 l# i3 r# j8 `4 [            //插入中间4 y+ Z  k7 `: |) J8 y/ X
                Node prvNode = get(index - 1);5 l6 J6 l( t( C- S& g4 B( K
                insertedNode.next = prvNode.next;
    7 o8 V9 Q& O, ?5 l4 Z1 i            prvNode.next = insertedNode;- y! F- ~& ]; M# ?7 F4 {
            }
    3 F/ S/ x& d7 M, p+ n& B6 @9 |+ {        size++;# {+ i# }' I2 i$ X
        }7 u0 g0 Z6 }% Y! c# @7 _
    4. 删除元素

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

    • 尾部删除
    • 头部删除
    • 中间删除  Z8 g" B3 V" P5 G8 S
    4.1. 尾部删除

    尾部删除,是最简单的情况,把倒数第2个节点的next指针指向空即6 W4 `  i. B0 l" ?3 \5 f2 o; O
    可。

    9.png / a* |) W+ ?- _* o  E  g5 U5 w

    * g6 s2 `6 l2 k: b  @+ |: S4.1. 头部删除

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

    10.png
    # b, @' ^; Z9 d0 T
    + J6 X5 P( h3 s; w" e8 W1 w6 c4.1. 中间删除

    中间删除,同样很简单,把要删除节点的前置节点的next指针,指向要
    : S0 H$ k2 H7 e# i/ b删除元素的下一个节点即可。

    11.png
    8 |1 E) T, p& \) M: G. b$ W; n! ~! r: x6 S$ H

    & R3 A7 I: Z  q% m这里需要注意的是,许多高级语言,如Java,拥有自动化的垃圾回收机制,所以我们不用刻意去释放被删除的节点,只要没有外部引用指向它们,被删除的节点会被自动回收。; J; [  C# T" k9 c" _! d+ Y; l
    如果不考虑插入、删除操作之前查找元素的过程,只考虑纯粹的插入和删除操作,时间复杂度都是O(1)1 k% f& o$ n/ ?# B0 L0 q
    /**' \% z# L/ ^. H$ S/ I: C
         * 链表删除元素
    8 K5 N* t8 H, X4 M( n' ]' F$ R     *
    / c) v9 s2 H* V9 T, ]) V     * @param index 删除的位置# C& H, H3 c6 t2 j/ Q* m. n( i
         * @return 被删除的节点" I% z* N! {) z
         */
    - j. Q$ Z0 u- E* x( N9 J    public Node remove(int index) {7 z+ l1 t8 Z6 K0 W% w+ V  {& W; r
            if (index < 0 || index > size) {
    ; S! E, i8 R/ R. `            throw new IndexOutOfBoundsException("超出链表节点范围");/ e: M- P6 g( t1 y
            }" K: \/ K0 W/ \+ [
            Node removeNode;
    . l' n, ]# o. ~! h, o6 s7 B        if (index == 0) {
    9 ]+ \" {7 h- `, ~9 Z3 P            if (size == 0) {, R3 {6 w, v" o/ R
                    throw new NullPointerException("当前链表为空,不可以进行删除操作");
    7 o* C; Y& L: i" J" ^, h' q2 H; |            }- J5 l% A8 f  q
                //删除头节点7 _, C: C# [2 W
                removeNode = head;" F) z$ f, \( w0 Y
                head = head.next;0 v$ ]6 I: U) B3 H
            } else if (index == size - 1) {
    # P4 Z2 h) l5 ]3 R            //删除尾节点/ m" H* A* L6 W4 M$ k
                Node preNode = get(index - 1);7 m7 c* |$ {# n; i( W* |
                removeNode = preNode.next;
    ) S. J( S8 o- w            preNode.next = null;( G2 X& E' E2 i" m
                last = preNode;; y) T* y$ G; t/ ^) I' w. k0 x3 u7 T
            } else {8 s1 a5 R! F; h, ^: O5 o
                //删除中间节点
    8 a" b9 K% p" m! K) j            Node prevNode = get(index - 1);
    . ?( l- t! v! L3 U0 L" S5 e            removeNode = prevNode.next;5 X/ z. [! P, D2 ~9 C
                prevNode.next = prevNode.next.next;
    0 D) u) Q# o9 H; y* J0 Z) n: u        }" }9 s4 h! c- u" Q
            size--;
    ; `+ s5 ]$ z' {  G! w& q% w' |        return removeNode;
    & l" d8 F! n" Q2 ?    }% p4 `0 Z- t: s: ?  A
    Java实现链表的完整代码package chapter2.part2;
    / G  B4 W. x5 X6 W: a" T! D$ X# I' k$ I: h
    /**
    ' Z5 n8 ]+ W/ ] * Created by IntelliJ IDEA.
    , q8 m$ Q; i4 p1 X *
    : J! V8 t  _4 v: L2 F8 ]' M! [ * @Author: 张志浩  Zhang Zhihao+ R7 y- Z* U1 F) ^$ c
    * @Email: 3382885270@qq.com
    5 x+ A: A" U4 e( ?7 {5 r * @Date: 2020/5/3$ P: [% |! K4 ]  }4 S( W
    * @Time: 13:39+ x) G" @  X' f
    * @Version: 1.0
    8 z+ E$ X7 T. L% B& Z; j! } */# ?% c# \8 f# Y' ]
    public class MyLinkedList2 {! e+ ?& l+ v/ d5 b  e) r* i% A
        private Node head; //头节点+ m# s- J1 B' _* x/ Y# h
        private Node last; //尾节点
    8 G( a8 X4 y) A: \; \    private int size; //链表实际长度( \% e- L, n- x/ F8 b

    0 F+ k+ q+ K- t6 s8 i9 a& g    public static void main(String[] args) {, f, Q  A! u1 ^2 T* j
            MyLinkedList2 myLinkedList = new MyLinkedList2();4 ]! H7 e8 a. J1 ?
    //        myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空,不可以进行删除操作% K: T3 Z5 i4 W+ f* {2 C  @
    //        myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围
    8 r( p; H3 }0 G1 {9 j* a        myLinkedList.insert(0, 3);
    & ]2 P0 ]0 Y9 C, g1 r# z6 w& Q; [        myLinkedList.insert(1, 7);7 a* x) e6 Q: ?4 G/ }% |* Q9 ^( T
            myLinkedList.insert(2, 9);
    1 ~0 V3 E4 S- K. U. C1 C" o$ [6 M4 L9 b        myLinkedList.insert(3, 5);8 X4 S) M& m. _0 i: ^. D  D
            myLinkedList.insert(1, 6);
    + P8 r) \+ e- C# F0 A# l' M) q# w        myLinkedList.remove(0);
    5 B* B8 b, f  X  T        myLinkedList.set(0, 23);
    2 f4 L: r& L; @7 f3 z$ j        myLinkedList.output();! S$ Y! e6 a" l' y
        }
    2 @% }- c1 j& N
    * O' K6 T2 M* ]- v( }- e    /**# m* ^  ~, n7 a; N) o! x7 l& J
         * 链表插入元素
    & W( `; X; o3 S. z' q1 d     *+ c' N1 g/ H' `$ S2 b& n3 r; P
         * @param index 插入位置
    % g' E/ J% Z2 }. m! r% L     * @param data  插入元素 被插入的链表节点的数据
    4 C4 O9 |) }! s9 x( M8 b" R     */
    ! U4 N# K- t; p% `( i    public void insert(int index, int data) {# F) g7 t% w$ H6 m  j+ Z1 v, m
            if (index < 0 || index > size) {; t, @) O, z& n. H7 n
                throw new IndexOutOfBoundsException("超出链表节点范围!");
    9 u6 g; r; U6 O/ F- \9 [/ a2 k        }  h7 z8 `0 i) n3 t  U% {. z
            Node insertedNode = new Node(data);
    ; M5 a8 x3 B% }8 r        if (size == 0) {
    2 r3 z( S6 r# a1 t8 B* I$ g8 i            //空链表8 a+ ?. D2 ~# C8 R/ B3 p1 d
                head = insertedNode;
    6 r, q7 P: h1 l) _4 q            last = insertedNode;
    * b6 A4 l3 ]( [. f2 \% Z        } else if (index == 0) {
    3 @8 s8 M3 |# z; ~1 b. \) T0 K            //插入头部! f% v- P$ l* F: f4 L
                insertedNode.next = head;
    7 M) n9 t- z; U            head = insertedNode;
    . \+ D2 o4 r: J, i" m" c0 x- z, l$ E        } else if (size == index) {
    & q* S3 S, E4 ]$ N            //插入尾部5 X# F  t8 q0 Q" w6 L% z$ V+ f* ^
                last.next = insertedNode;
    + `: L/ i$ o( O* B- E% O            last = insertedNode;  g7 v$ g9 k5 Q8 X: Y
            } else {3 Y: Q) q! K2 [
                //插入中间6 B& c7 y( w. e. F3 C
                Node prvNode = get(index - 1);
    9 J9 X/ h; c, V: u, U. {; Y8 S            insertedNode.next = prvNode.next;& J' s! e1 i+ D+ @: P, ^. m
                prvNode.next = insertedNode;
    9 Z) E, \* Y- h        }3 M: y- d' Q; v( \1 z
            size++;7 X1 M7 W0 g% P4 G8 G- R
        }
    : u. s* T6 Z& j5 c
    ( a8 n2 ^# [# Q: i  H# P    /**
    1 {2 V  M; e) b2 V# V     * 链表删除元素  N! y# R$ a- A2 }3 ?
         *
    9 }/ n" b* o& s$ u7 T     * @param index 删除的位置1 |$ C/ I6 B; ^- w& x; q
         * @return 被删除的节点( t6 V. B1 F8 D$ {$ |" Z0 W, F
         */3 G. @! M( E  j  u( F4 [$ d+ @
        public Node remove(int index) {
    5 L8 c) V, z+ o3 C        if (index < 0 || index > size) {
    & S6 ^! Q4 j) b4 E3 e) P            throw new IndexOutOfBoundsException("超出链表节点范围");1 O9 N& n: ]" u& l* t
            }, W! m/ y" E) }' q% j8 J. p9 n
            Node removeNode;
    9 D* q% y; W- }6 X; c        if (index == 0) {1 [7 e  z% |2 j8 G
                if (size == 0) {! _3 e, S' I8 ?
                    throw new NullPointerException("当前链表为空,不可以进行删除操作");
    7 s, R7 X! w$ W8 ~3 C            }
    2 n) T1 |# Z. W6 E: _2 r8 j% f            //删除头节点. z, w9 l. S+ U- ?  T' V5 A$ U7 x
                removeNode = head;
    7 Z. R% l- r; w3 }2 t8 F            head = head.next;* f. ~7 K, t6 B: J" @' n
            } else if (index == size - 1) {
    : ~" G7 @; ^2 I2 _" i* Q            //删除尾节点
    : F- b- W7 u( i* D  Q: a            Node preNode = get(index - 1);# g  ^7 z. X& [9 T9 h0 Q1 Z# w. [' h
                removeNode = preNode.next;
    " m; e# F% N1 u& E6 z            preNode.next = null;& }- c2 U' C5 i1 c8 n
                last = preNode;! n' I( X# n/ c" v2 h4 J6 I2 R
            } else {
    % h, T+ d2 S7 S# V  s4 d/ A            //删除中间节点$ \: i  _* q9 U
                Node prevNode = get(index - 1);
    + s0 e& d/ U) y            removeNode = prevNode.next;2 ?1 q+ h& f. n! C5 j2 [3 ~& ?% e
                prevNode.next = prevNode.next.next;
    : f6 u% y% F0 j& V2 {0 f        }  {9 p& R1 }6 P
            size--;9 s' r0 N5 |4 H0 i
            return removeNode;( {5 e- F4 ~2 C
        }* i) v' z% Z4 _( D

    6 g$ K; C% H- r* E4 z( M    /**- S; d7 t9 H  S
         * 更新节点 将列表中指定位置的节点的data替换为指定的data。
    8 x# c: ^) D% @% B3 U     *5 k& L/ g' `* |
         * @param index 需要更新的节点的位置
    * a! Z% Y* P( ]     * @param data  新data
    $ }9 c3 }4 A8 \" ?/ d  t     * @return 旧data
    % e% m0 h2 P' W0 Y' X$ t& p* i     */
    . Y4 h' G2 a" E5 X# `7 x6 g( j* v    public int set(int index, int data) {/ ?# _) z3 ^3 L' i& t1 S
            Node x = get(index);0 y, N% b) p5 ~! J- Y4 I
            int oldVal = x.data;
    ' J! w$ m: ]! q% T8 O& j; }        x.data = data;
    $ b& s9 \; S) S7 i        return oldVal;& H. d% b' ?: ?0 V: `' f
        }
    1 N1 ?, `+ t* H4 O1 e! v
    * {" `4 a2 a6 P2 t4 ]. C% v    /**
    4 H8 {% v+ O# }8 E9 Q     * 链表查找元素% @4 B& u, T! Y+ L7 z. K* ~, L
         *3 g$ N4 S* v3 p0 }) L( z& V
         * @param index 查找的位置
    , C4 j. U5 s+ n% o     * @return index位置的Node对象  v$ `$ {5 G9 M' e+ A& ^
         */
      A7 F, n. g2 p% K; D) t" R    public Node get(int index) {0 L6 e  v% D# a$ H6 G. L
            if (index < 0 || index > size) {) ^, p, p* d8 f, |
                throw new IndexOutOfBoundsException("超出链表的节点的范围!");6 I9 i' j  G$ D- R7 {* {
            }
    . z4 C% k7 D3 _0 J$ G1 V        Node temp = head;( X, W8 X0 O( x5 U) ?
            for (int i = 0; i < index; i++) {
    2 Z" a! O+ v  z" ^: b            temp = temp.next;
    0 {9 k) ~. ~2 G        }
    ( y; r! d1 X6 v( S5 t, C2 E        return temp;
    ( R- n) M" |2 P# z9 \7 M5 {3 J    }
    9 O: X4 s  J0 ]7 P; b& t3 _+ j0 o) z& Z$ m
        /**
      {6 e* D# H$ i% ~0 J     * 输出链表  O: n& V" M1 X  Z2 k
         */; Y4 s, z5 j+ J' c% F
        public void output() {6 F2 [0 B, _# ~! @
            Node temp = head;8 ]5 N0 n- j% V) F! b$ w$ c- g
            while (temp != null) {. q: _8 `" i+ o" Z& B7 M& U6 I/ Y
                System.out.print(temp.data + " ");1 t4 Q6 K+ U: a' s, Z7 t, s7 [
                temp = temp.next;
    8 t9 Z. \8 ]! Q: R, a        }
    8 r" _* d2 R) U1 y    }; E: |; S, M- |. T

    & [& L7 ]8 ?! g: O3 G: ]$ D& a9 K    /**/ G! H4 f7 N0 e0 j
         * 链表节点
    / U! Y. W* y0 T# S4 D+ {     */
    1 L* j4 t% g+ S$ `  h& F3 ]    class Node {7 [" `" c3 K8 X
            int data;- _" v! {$ P8 u. A1 \) v
            Node next;
    5 v3 T) `9 \# R8 a3 r3 g  z3 k2 G9 p0 D/ Q
            Node(int data) {
    8 Y8 ]5 B# B1 ^0 \$ a            this.data = data;
    5 h& ~5 E5 l6 a  S1 K        }8 U/ [7 o& A5 W- t, D: c/ U/ y
        }
      m; t: t. |/ B! Q9 A}; D9 @/ j8 w5 Z3 V8 Z3 q
    : ~; {# B; y; X% g; N6 e

    " q! U' j4 g, ]! f二、双向链表 12.png   }* \4 r2 N/ w9 p
    双向链表比单向链表稍微复杂一些,它的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev 指针。3 t: q: R, L  P  |% v5 d! w$ s7 ]

    / g' Q3 O/ t' K5 @5 Q
    $ r* [9 k. v7 e# j6 s& `. R" G
    . ~1 T- B' ^9 r6 H
    ! N+ P, z+ {! s————————————————
    " M8 f  W9 A! M版权声明:本文为CSDN博主「爱做梦的鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。% R7 E& f' j9 _8 K- J, E* x
    原文链接:https://blog.csdn.net/weixin_43124279/article/details/105904468
    . K1 D: N% Z5 i8 k: A
    4 Y" G! d& N% W9 F  {0 d, [* |/ r/ o% w3 ^

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

    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, 2026-4-20 01:46 , Processed in 0.407443 second(s), 54 queries .

    回顶部