6 ~% v0 `! h/ ~' I【Java演示】什么是链表?数据结构
* u! W8 H; }6 q* d! {1 _( J% d& R一、单向链表
' s) Y ~7 k" R
4 Y6 c! X$ B+ |0 |
8 M) ?7 f' e3 Y# I: F链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成。8 ~% a5 ?3 U% ]3 c7 o
单向 链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next。. g& u- U6 ?( y' e5 _- w+ L
链表的第1个节点被称为头节点,最后1个节点被称为尾节点,尾节点的next指针指向空。
5 Y- I/ r2 t0 M. p R5 X) Y6 w9 @( E) ?7 C$ G2 ]: A
什么叫随机存储呢?
4 \5 @% p& H. v. }: t1 F" W# M" H! q" Z$ v
如果说数组在内存中的存储方式是顺序存储,那么链表在内存中的存储方式则是随机存储 。: _: O0 [5 V& Z5 R8 ]" [, S
上一节我们讲解了数组的内存分配方式,数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式,链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。
3 d1 q8 }/ @- i, b* C. }
7 @/ g; B+ O; e1 F% v. R7 g4 o" j8 K3 p ?0 `: a
图中的箭头代表链表节点的next指针。 链表的基本操作1. 查找节点在查找元素时,链表不像数组那样可以通过下标快速进行定位,只能从头节点开始向后一个一个节点逐一查找。
6 b2 B1 j z. E7 h/ i8 } `! t! u
" W) |2 p/ ^# U7 @1 _5 B- {1 B/**, l* l' t# n9 K( V) b
* 链表查找元素
, ~9 J( O' b# R& O- g* W; F: j *) A/ L( f) }3 @- k5 G" V' `
* @param index 查找的位置
) g9 E# g2 O' V4 J * @return index位置的Node对象
/ @. _0 B W6 ]( r, _ */- S/ R" V5 Q/ s9 w5 S
public Node get(int index) {
! u% {- V( |, I& _! g7 y" Z if (index < 0 || index > size) {
- P% ?+ D9 q* U throw new IndexOutOfBoundsException("超出链表的节点的范围!");
. q1 d0 l/ F) c- p% ~% w }
4 n4 Z) {' w/ n$ s) B5 U# E Node temp = head;$ H, K1 U4 `* `' U
for (int i = 0; i < index; i++) {' z6 {3 P& J' b
temp = temp.next;; T# l1 a$ ~+ t3 | ^% w
}, m& D! R# b- P1 c. s0 J
return temp;% O2 K# F* q* e: F2 I: l L1 C
}
+ |3 Q) w l9 ~$ }' ~6 }7 N& `+ V+ ?: q. D; F; O" h) b
链表中的数据只能按顺序进行访问,最坏的时间复杂度是O(n) 2. 更新节点
- P5 c8 x" ^ I8 s7 k
# E. S; {- }, o# m) N+ l4 }7 u. Z如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据替换成新数据即可。
" C$ X0 f; K$ |1 @* z9 x如果不考虑查找元素的过程,只考虑纯粹的更新节点操作,时间复杂度是O(1)
0 ?+ h" N! a' s! v, |& N# m' K/**
Y2 j6 L; q4 |+ J8 g2 @ * 更新节点 将列表中指定位置的节点的data替换为指定的data。
7 ^% A& I, g* i0 o& F- Q0 h *
( b, }/ R1 r7 r; Z * @param index 需要更新的节点的位置9 w$ c. ^2 R: w6 E
* @param data 新data
- T5 z* }( Z( Q7 ~" T7 g7 d * @return 旧data
! _7 W' V+ n+ n O */( U. h5 V& I$ G0 e2 N
public int set(int index, int data) {0 Z5 c. B9 {, K- l$ c+ } y, @5 `
Node x = get(index);
4 w9 b/ @5 W- V% M int oldVal = x.data;6 l, J1 H, |, K! S( @
x.data = data;
8 w+ H# l' L! \ return oldVal;7 I$ c4 g# a+ _
}5 \; }9 F& f, e; @ v$ p# x. ?5 G
4 G( C+ Z" l* \) n2 h1 O4 e
3. 插入节点只要内存空间允许,能够插入链表的元素是无穷无尽的,不需要像数组那样考虑扩容的问题。 与数组类似,链表插入节点时,同样分为3种情况。 - 尾部插入
- 头部插入
- 中间插入5 d4 M4 p7 G% ]& N2 P* i
3.1. 尾部插入尾部插入,是最简单的情况,把最后一个节点的next指针指向新插入的节点即可。 8 K6 o1 _* ]2 O2 n$ }- S5 W; [
# |$ i1 A; z% a% d3 l
3.2. 头部插入头部插入,可以分成两个步骤。 - 第1步,把新节点的next指针指向原先的头节点。
- 第2步,把新节点变为链表的头节点。4 J& M7 H/ D' ?8 w8 b. W
# c [2 b8 i+ m( `$ J9 t
; a6 j* F* ?! a4 y3 H3.3. 中间插入中间插入,同样分为两个步骤。 - 第1步,新节点的next指针,指向插入位置的节点。
- 第2步,插入位置前置节点的next指针,指向新节点。" S* e0 x# T3 n1 f
' s2 s" |% d2 v/ F# m8 w
/ U" ^+ ?0 Q# `0 f: @" f
三钟情况的代码合到一起& l# x% X7 b3 t* F! |$ G
% k5 Y1 c% y! _& T2 R. S
/**
) [, G6 w7 ]$ t * 链表插入元素
& J9 x0 s/ ~% P A: \2 V8 z: Z *
$ h' ~$ N% \9 o ~7 w * @param index 插入位置8 [, G- Z& y' ?$ i
* @param data 插入元素 被插入的链表节点的数据
- }7 c$ ~4 F2 H! I8 |( v' t- i */& s8 z! X- i5 Q& R% I }* H) {+ L
public void insert(int index, int data) {8 [0 L# h B: {3 G+ f, J3 V
if (index < 0 || index > size) {
1 r! J6 a# g$ d m throw new IndexOutOfBoundsException("超出链表节点范围!");5 ]; Y# S+ [* @- w% p [' V% C
} T& O5 K; |1 b1 m4 p. p( s; P! s. ?4 ?
Node insertedNode = new Node(data);
% n4 u6 s; k4 @: `/ X if (size == 0) {
) _ G1 N" |' \9 F. @ //空链表, d7 `% W. U+ V6 ~% M5 n
head = insertedNode;# y3 q3 ~6 g" z1 z7 ^$ Z& t
last = insertedNode;
& y8 ?) k, L F z& O: T6 T# k } else if (index == 0) {0 B) p f0 Q9 c2 P: ]* [: Q
//插入头部$ ?0 X; p- m4 A5 c
insertedNode.next = head;1 [! @0 w, F( u# Z3 z- G& x# i" R( ^( p
head = insertedNode;
5 I3 C' R- K& K1 g: V f! k' e2 R } else if (size == index) {$ b! X7 ?6 t/ @; t% ~* j/ t" E/ O& j
//插入尾部
: v9 p, I0 f' s' ? last.next = insertedNode;
2 `0 Y* ^6 K$ B4 o last = insertedNode;0 t7 d& V" \# q) W. t
} else {
, |0 L" e6 j) G* v" b/ y h" [/ s# F* S% C //插入中间
- r; i6 J0 A: T& a7 M5 r7 K( Q Node prvNode = get(index - 1);
# X l w/ U6 P1 N* o insertedNode.next = prvNode.next;
# C& S; R4 b* } prvNode.next = insertedNode;
8 a0 o2 _- Z; p; a$ ] }, Q' `$ S5 I# ?& K5 A* ^0 [
size++;
; b/ J, j- ~* N+ o$ l3 O }
# G/ |2 |# O2 e7 [6 s, L9 F
& V& z& W2 [+ y$ X* N5 ^7 e/**
6 w' O# v7 i1 \) R% C. l3 J * 链表插入元素
Q- t" e4 ?! o# _# w# R, A *
+ f9 |# U% \: \# W' }' | * @param index 插入位置$ ]7 S2 U h/ e' r: D: j% r
* @param data 插入元素 被插入的链表节点的数据. K3 K- `; p" G: Z- m
*/
' i% t! l% C8 H) Z public void insert(int index, int data) {
5 r7 }) [; w' c+ l* H7 B/ C( P if (index < 0 || index > size) {( O- E* k- |+ p7 ^3 j% g
throw new IndexOutOfBoundsException("超出链表节点范围!");
9 T0 \1 V" q2 V3 h a# C9 t7 Q }' n0 d- b3 p( _& H+ Z) u
Node insertedNode = new Node(data);
( s" V+ x7 {; P" e) | if (size == 0) { A# e/ d! W1 g' _4 B. w1 H
//空链表
, f# r; R* F5 U3 V @ B! H# o8 \5 \ head = insertedNode;
& m. w0 B2 A4 |# L+ T last = insertedNode;
* X6 }7 Z7 [( C' P4 { } else if (index == 0) {
1 [% L; H3 O# U( s //插入头部
/ q. x8 B7 h% E* s: C- o) y2 g3 |" V8 I insertedNode.next = head;
( V$ `$ g5 ~9 E. {6 q {6 X head = insertedNode;
! |. G9 O+ y+ D) w& a/ K% F } else if (size == index) {
& X% J( t2 B1 ~! d //插入尾部$ U, K& x0 _. y3 Y* o
last.next = insertedNode;& w& s: ~" r3 n5 X7 P8 I, m
last = insertedNode;
) u$ G+ f$ s4 w$ t! {/ Q } else {3 o" }9 Q! m2 F# z1 N
//插入中间' I1 W3 @$ ]4 x
Node prvNode = get(index - 1);2 g2 _% T) `) o0 B6 M3 S+ t
insertedNode.next = prvNode.next;
: ~! M1 l3 ?' ^1 u7 v prvNode.next = insertedNode;
- T) S: z! m* G1 e# L }
4 o/ n& p% g' @( d size++;
# w& T" V- p8 R5 x, q6 X+ y }
5 C! @. C7 s( F0 b: }* P; ^/ \4. 删除元素链表的删除操作同样分为3种情况。 - 尾部删除
- 头部删除
- 中间删除
6 N1 `# H4 ?# ` V- s. q. ] 4.1. 尾部删除尾部删除,是最简单的情况,把倒数第2个节点的next指针指向空即
! i; ]% F, K" z( R可。
) O: T# W, f# S4 M
( {. O# V8 y M9 [9 f4.1. 头部删除头部删除,也很简单,把链表的头节点设为原先头节点的next指针即可。
2 K9 N* S7 y. @9 d- n! A+ x
# L3 @+ D- d) @) [. h# M) I% ?
4.1. 中间删除中间删除,同样很简单,把要删除节点的前置节点的next指针,指向要/ ]& v' P' j/ [
删除元素的下一个节点即可。
2 W* v9 h8 L) v! p3 O
5 h! ^4 r4 C( t8 k- J! I6 P
2 `* B6 p9 d- |+ U9 L" B# F- l这里需要注意的是,许多高级语言,如Java,拥有自动化的垃圾回收机制,所以我们不用刻意去释放被删除的节点,只要没有外部引用指向它们,被删除的节点会被自动回收。
2 _6 @1 X' g) a如果不考虑插入、删除操作之前查找元素的过程,只考虑纯粹的插入和删除操作,时间复杂度都是O(1), A4 F! _! J* {( o8 I( m
/**3 s ^0 q: l# m! n# W1 i
* 链表删除元素3 A, x- e) m% j+ Y- {2 E1 N
*9 k8 E* U+ R5 k4 ]; R4 n* F
* @param index 删除的位置9 `/ o: {$ {9 P. W
* @return 被删除的节点. U7 c/ |7 S3 |7 o8 b+ }$ H
*/
! l% {1 [, b) i* E public Node remove(int index) {
$ e# D6 ^& o# { if (index < 0 || index > size) {
+ Z- M6 w+ Q2 O5 r b0 a9 e V throw new IndexOutOfBoundsException("超出链表节点范围");
1 A, |0 D' f; h# L ^, s }( X& h) O/ L. y8 ~* ? l6 p
Node removeNode;
9 b1 e$ U0 g6 f if (index == 0) {% s9 p/ t5 T, e1 Y* v1 ]1 e
if (size == 0) {
* T. c- M6 W% [% K6 C throw new NullPointerException("当前链表为空,不可以进行删除操作");
I, C' W& V( Z/ C2 ]2 w+ q5 _ }+ ` n2 i8 ~3 ]$ w% T
//删除头节点
7 f8 C9 V0 j7 p. N) C removeNode = head;: l8 o5 y3 g$ W
head = head.next;9 o# Z! s z2 r! Y
} else if (index == size - 1) {
* }8 |* c; g, ?" `& a% j //删除尾节点/ T) z- Z- Q5 D4 Y8 _
Node preNode = get(index - 1);
4 s0 Z; J" m6 q- I1 J/ C removeNode = preNode.next;
5 {$ r2 e4 f* K" v8 g3 C' [ ? preNode.next = null;
5 }1 ]' \, l( ?: c) r last = preNode;" f6 f2 N+ c" L4 w ?
} else {) H2 {! q: w- I
//删除中间节点
3 q; @9 R/ l i( h Node prevNode = get(index - 1);
# O( N' l! m1 N' i0 n removeNode = prevNode.next;
7 Q S6 l, y W3 A) w+ g prevNode.next = prevNode.next.next;8 W8 H) O9 l% G
}
) e5 `) a' T T$ W size--;; O: u$ M3 C7 {( D& y; B
return removeNode;6 @) B- X! `/ \/ I: F1 E0 ?
}1 @$ g: S! G+ O0 ]" @
Java实现链表的完整代码package chapter2.part2;
- }* [$ ]6 t% q" J' \1 j
0 i' B! \1 w. R h: {% g0 q$ Z/**$ g6 z$ b* a3 z' B) k4 J9 F
* Created by IntelliJ IDEA.
( p6 X N; D Z" _. a5 I * C/ P" `+ i+ ?: \) i' E ~
* @Author: 张志浩 Zhang Zhihao
- ]. h- C+ D+ S2 l: X; k * @Email: 3382885270@qq.com7 U4 e- \- I- P9 `1 q: x7 _3 g
* @Date: 2020/5/3
, E: F; Q& ]0 Z) f * @Time: 13:39
# O+ N- P+ y/ e5 } * @Version: 1.0
7 z* `% ^' O, R0 J" M */
8 K9 h! t! Y( ^) Apublic class MyLinkedList2 {( j$ G! C7 I* Z, e2 B
private Node head; //头节点
, i/ N! V5 [( V6 }: ~ private Node last; //尾节点& ?) s9 D& X5 k, P# L
private int size; //链表实际长度
) [# G. U8 q Q% @- U2 Q6 w/ B
B' V: v$ x" P8 K b, a public static void main(String[] args) {+ c. k. j& h7 ?/ y" U
MyLinkedList2 myLinkedList = new MyLinkedList2();
" x* R5 }9 s0 v; G) t, S0 ]6 T// myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空,不可以进行删除操作8 z% F" }2 w, m* ~
// myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围
' [& E! _- a$ g" U4 ~) @* Z: V myLinkedList.insert(0, 3);
& b1 c0 n4 ?. X" X& m8 P myLinkedList.insert(1, 7); T6 U+ O8 V8 t3 Q1 t
myLinkedList.insert(2, 9);2 Q3 W Y: l# F7 o8 |& U
myLinkedList.insert(3, 5);% J+ U4 y% P9 U; x
myLinkedList.insert(1, 6);2 H0 C F2 F! h5 l8 S5 _; `5 t
myLinkedList.remove(0);
% q6 d. o$ j( H6 L6 B0 X myLinkedList.set(0, 23);" p0 u4 I: h( w( P: m1 |
myLinkedList.output();( p! W7 z) }& u
}! Q6 `5 ^1 W7 ]7 D7 T, w
L$ r' \" m; [+ b /**4 w! [" ^) u; p" ?% r) D5 c% v
* 链表插入元素0 U! A! f: J. k' z5 Y
*
% T- k! m) x7 e2 f( n9 a$ R$ n * @param index 插入位置! }$ m2 G1 E% L: o5 N% R8 q) X3 A( ~
* @param data 插入元素 被插入的链表节点的数据! V# H* i, ?% z% [+ L6 P/ d
*/
4 N7 L, C$ j. _ N public void insert(int index, int data) {/ E# s) D7 @- E4 q
if (index < 0 || index > size) {0 A" [- e* Q+ J
throw new IndexOutOfBoundsException("超出链表节点范围!");
: I9 `7 w4 K7 p$ Y1 Y }( w3 L% X* K* E
Node insertedNode = new Node(data);- Z2 F( o8 f$ i
if (size == 0) {. x5 ]! A0 S) V& }9 j
//空链表 q1 E6 u1 t& K" n- g
head = insertedNode;6 U" E, |- Y1 l* Z( Q
last = insertedNode;9 |4 {! y3 B! v+ q/ ]
} else if (index == 0) {
5 o v' L0 P* |5 F* ^ //插入头部
- j; H% t. l$ ]- a4 @6 _ insertedNode.next = head;
8 C) d, F/ e3 P: X% b head = insertedNode;
+ T: r R. h" {3 B } else if (size == index) {
: B: W" k0 x: I6 z7 J1 C$ A r //插入尾部) T4 O) I$ W! W! b3 V; [" a
last.next = insertedNode;2 }" A* p# Q3 b) o! J/ Q4 m
last = insertedNode;; U8 E* }2 }- A. ] R
} else {
1 T, }4 c' Y' n) [' t3 w //插入中间$ p8 x" c& p Q. q) F9 E
Node prvNode = get(index - 1);
/ X& T) K4 [3 y+ D insertedNode.next = prvNode.next;/ z+ N6 B: j ^8 e' g V
prvNode.next = insertedNode;5 K" e1 r8 p, J& n
}
! K6 {) H1 a0 r: {% E% Y6 U size++;
* p4 i8 V+ X3 X3 r0 c }
# z& d; A# G# N2 `9 x. o+ m. i4 }" q
/**
- A, k9 [7 H8 q7 w5 R6 j * 链表删除元素
9 |" w7 l/ h( ^$ a5 k *' u6 c0 T9 C8 Q% _1 g$ m! n9 L
* @param index 删除的位置
5 M6 _' t$ B" r9 X% T L * @return 被删除的节点9 w1 G* x6 b) a, M" g0 R
*/
: S8 l g9 {- S public Node remove(int index) {4 ~7 Z1 H; S) y7 o+ Y9 j8 v
if (index < 0 || index > size) {
8 } J& C6 D- ?, S throw new IndexOutOfBoundsException("超出链表节点范围");
8 h2 r/ g( c7 q, { }
% L" d; j8 a$ \. g* j4 \; D$ } Node removeNode;
4 R6 a V1 r. c4 V8 R. x0 H if (index == 0) {
4 a6 h5 T4 x- D6 ] if (size == 0) {
3 O& m5 G1 T0 i! P; t6 a throw new NullPointerException("当前链表为空,不可以进行删除操作");
6 Z* U5 l# G3 A/ ]! n }2 a9 s/ ^ `$ P' P8 u, |
//删除头节点
# V& P$ ~0 f- u6 Z! P removeNode = head;1 {7 u0 r8 W% l1 o
head = head.next;9 s, T* |; m% E- A7 t9 X6 ]
} else if (index == size - 1) {
* D0 n, T) _& y) G; F! _, { //删除尾节点
3 ?/ X+ O/ A. B+ Y5 {0 \ Node preNode = get(index - 1);& V Q/ x1 ~3 \( o* p( M
removeNode = preNode.next;- g% }: W8 a1 K9 j; b* f3 h
preNode.next = null;
5 t) U& Y+ ~: B' t last = preNode;4 R8 S( \5 X% S# L( J
} else {$ y# M7 f4 l" T( Y& D) `# w% S
//删除中间节点" B: M) J L1 e5 Q* `+ F
Node prevNode = get(index - 1);
. S! X: x: j2 \ removeNode = prevNode.next;7 s9 c s4 v& M) K
prevNode.next = prevNode.next.next;% W5 ~& \9 D' ]5 A! J! B/ ~$ i
}
0 M; b5 ^ s5 z: `5 J size--;
! \9 R& u& L5 Y1 l2 L0 ?$ A return removeNode;
2 Y! e* D' K5 G7 P, }+ q1 \ }
5 F2 ?9 c0 B: g" T* E8 V! V1 Q7 o' } x* x. D
/**
7 |) X+ R7 _* \% r( k2 _* }; I * 更新节点 将列表中指定位置的节点的data替换为指定的data。5 k/ Z# G( f4 X
*7 P7 V9 R8 w$ e; E: Z [1 J
* @param index 需要更新的节点的位置3 c2 D' f' x# v. a" [9 H
* @param data 新data# D# i1 E3 e& d3 X @$ o! ^
* @return 旧data' ^) P$ b% o* p0 Q' ]
*/
5 e8 C7 U' m, V* t public int set(int index, int data) {% l5 z5 B+ }# i6 J) n! @4 c, A
Node x = get(index);
# d6 k) ]8 {7 Z int oldVal = x.data;9 k+ e1 p- P# ^. q5 I4 R7 l6 G" t
x.data = data;
9 T) S1 B Y+ ^ return oldVal;* e8 S# l D$ d! d$ i, T3 j( m
}
+ x6 l, m& d8 I/ x5 p
: n" M+ q7 A- l& R* E0 y" { /**
* R( h6 r( c9 [ c9 L" `. p * 链表查找元素+ n4 E8 S7 J1 u& P" u8 m5 i
*; \2 n$ B6 K* c: ^( Q: g; x2 V
* @param index 查找的位置2 d; i% f6 W8 [" i, d7 \6 E% v
* @return index位置的Node对象
2 J7 o% ^# C' W- s; {- n, `+ M */1 T) e$ S' R3 Y) n ]
public Node get(int index) {
5 }! K: y( t, |+ | if (index < 0 || index > size) {4 j) |* {9 c1 U: `9 e; B7 V, _
throw new IndexOutOfBoundsException("超出链表的节点的范围!");4 A0 Q( q) A0 l. A% v% k
}
* i1 v$ `% J3 V9 T4 @! T* S: c Node temp = head;8 ]' ^( l7 T; q
for (int i = 0; i < index; i++) {7 F! ]( x3 }5 }; }5 |+ x' H! |
temp = temp.next;
' B2 o$ i2 X9 O8 I6 C6 S' ^# @ }
; o6 H" x2 J; I' p- X% a. P; n return temp;
8 N) _; K1 B2 v7 T D* r4 o }
+ q7 Y& ~7 M( y6 N5 Q* J! z! ?2 [/ q6 X0 g# j
/**
. `# ?5 b% y2 J8 }4 s; }% r% ` * 输出链表 p3 u2 t; I8 d+ p1 l1 F
*/
) e% J2 }1 J0 M! B public void output() {9 T5 M. t& @! D2 g- M
Node temp = head;
' E) f9 x2 ?& {8 C' S' ]1 s while (temp != null) {, G- R. Q* G$ s2 k2 a2 Q1 Y
System.out.print(temp.data + " ");
9 o' o2 K. u& C$ f8 i1 C# N& A- T temp = temp.next;
+ r5 o6 n; Q4 j0 \. w# _* M }
: _2 A4 ~" T& q) [ }
, X2 {4 p3 H* V9 }! N: `4 u- l) F; ~+ `- C3 f6 Y7 ^$ E; M2 R( c- b
/**
, D% C+ p% Z9 K0 @3 X. n6 q. J; h. @ * 链表节点# b8 @) x, D3 S; H) Z2 ^2 \
*/) I o. n( W- l" k3 Y( Z8 H+ I
class Node {
% }! L, j+ r2 _! Y* l" v* E! ? int data;; y, Z# I1 c" b- z, X b, l0 D
Node next;
4 H/ N/ }0 t: ]5 E* \) x8 O) L2 d: e/ }* o6 ^% V7 e! f
Node(int data) {1 ?* H- C( X. V4 d1 T& L0 t
this.data = data;
8 I0 c4 w* X' t4 A$ j }1 u% N P/ `; D. a8 u
}
5 q1 r u/ Y( u0 C}
( H" s, S P( Z* d9 U- p' t* K: h2 B* q! e
2 n5 l; Y& [" V5 t" K& ^2 l( p- i
二、双向链表
5 b s1 u4 s( x" v6 y" u! }6 U双向链表比单向链表稍微复杂一些,它的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev 指针。
' b8 R. a; ]0 ~" f) L8 \
+ \, F3 X; I. M# C) b
# g5 S0 d4 j2 i4 {- N
- o8 g5 N+ p& `* T- y9 a3 H( _2 |2 B7 x/ W
————————————————
) z' y+ s% H v版权声明:本文为CSDN博主「爱做梦的鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
/ {! T7 c3 H0 i" _6 Q1 l5 k原文链接:https://blog.csdn.net/weixin_43124279/article/details/105904468
/ [( I, X. \, d; c
) G7 T" E1 Q) m7 C7 B( V
& `; Y) v! \/ O0 I& r1 I |