数学建模社区-数学中国
标题: 【Java演示】什么是链表?数据结构 [打印本页]
作者: 杨利霞 时间: 2020-5-4 15:55
标题: 【Java演示】什么是链表?数据结构
- n( O2 _% H4 M7 S( ^& \【Java演示】什么是链表?数据结构* m0 o: ^' ^) g7 I: M" _& n
一、单向链表
9 G& {* z, p) e9 Q, j; m- T
! b% K. x9 s' e+ y# ~9 U' F
: u- Z' |0 w, F* e# c# R1 p链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成。
; T2 h0 M! P0 N5 X6 w- a1 I单向 链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next。6 ]0 O2 Z/ H8 P c% T+ L+ ?
链表的第1个节点被称为头节点,最后1个节点被称为尾节点,尾节点的next指针指向空。
v) \! D6 d( H$ U5 K& o. M, f( s# [6 h- f/ c. }/ p2 |, I
什么叫随机存储呢?6 Y# [& m8 R$ z6 h) Y( O# J- r
# i, R* r2 d q7 \1 ?) D9 U如果说数组在内存中的存储方式是顺序存储,那么链表在内存中的存储方式则是随机存储 。
& d& o6 @7 a. R2 d' s+ y) G上一节我们讲解了数组的内存分配方式,数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式,链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。
: y: e! g1 W& I( n9 ~
! J W$ Y4 k$ c+ r7 ^ A* D
( d6 h' j t- k' m5 ]9 a' @" A
图中的箭头代表链表节点的next指针。
链表的基本操作1. 查找节点在查找元素时,链表不像数组那样可以通过下标快速进行定位,只能从头节点开始向后一个一个节点逐一查找。
6 O! U7 o4 u9 W2 \
( c; v# ~7 r* m! D3 R$ m: e# k/**( a3 ]8 [% H3 o/ Q5 ]3 g
* 链表查找元素
' v. a8 d, {5 l1 ?& n* L) M *
$ S- Y% t; [9 N4 q: @+ b * @param index 查找的位置, X9 L, S: C) m+ y" a
* @return index位置的Node对象4 T& E; x; I6 `0 Z8 s7 ]
*/& T2 u9 P/ l4 s: l: j
public Node get(int index) {9 r* `" q4 u' a+ G
if (index < 0 || index > size) {
4 ]+ g/ d, J4 Z+ R" d throw new IndexOutOfBoundsException("超出链表的节点的范围!");( }. E' u. \( K- ?
}7 u$ M ]0 o6 b) Q# E. G3 S
Node temp = head;; F' i# {& ]( h2 S" k6 Z
for (int i = 0; i < index; i++) {
0 F. [! [& Q- I temp = temp.next;
& D9 W4 Q i: q: t- j5 p. M }( m1 _. J: d# l- {8 O; i5 `
return temp;0 }8 P, O+ S! N+ g; B3 h' Y* i, o
}
8 G9 S$ s6 x3 G2 H6 E* X9 ]
1 A' l. i6 @% `( L& a链表中的数据只能按顺序进行访问,最坏的时间复杂度是O(n)
2. 更新节点
8 d0 x' v" z( F7 e% ~
, r+ L* e" `& `+ T如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据替换成新数据即可。: i6 S' `9 E( r& i3 P- S \6 [, o
如果不考虑查找元素的过程,只考虑纯粹的更新节点操作,时间复杂度是O(1)
! k; O m% X @! [! M! H/**
E% V9 d# N' v9 ?. q * 更新节点 将列表中指定位置的节点的data替换为指定的data。
5 f. P4 t9 n, d0 Q9 i; E p3 n *' w& a% U5 ~! Z& G: R+ d
* @param index 需要更新的节点的位置6 L9 c& _( {1 Y. K
* @param data 新data
0 j+ f* ]6 a3 m7 Y/ u * @return 旧data
8 g8 M2 e. D$ c6 a( A' I */
: v9 m- @- H5 p public int set(int index, int data) {
- m5 d5 v& t6 Z" @9 K Node x = get(index);
1 [; |7 k& U5 g* z- K, \1 L int oldVal = x.data;
% o$ S1 _5 u5 V O. M2 A: v* u x.data = data;: P' ^2 t( u# T \( o
return oldVal;
/ D1 O! i% x( H+ b+ H }) o( v" L/ G/ [2 O! q; U; p
9 K _# q G! A9 w0 x1 L2 o. \
3. 插入节点只要内存空间允许,能够插入链表的元素是无穷无尽的,不需要像数组那样考虑扩容的问题。
与数组类似,链表插入节点时,同样分为3种情况。
- 尾部插入
- 头部插入
- 中间插入8 J5 K J1 K5 R; k3 U; X
3.1. 尾部插入尾部插入,是最简单的情况,把最后一个节点的next指针指向新插入的节点即可。
" {/ }: Y4 F7 L
4 s& L5 R* E8 Z% K$ g3.2. 头部插入头部插入,可以分成两个步骤。
- 第1步,把新节点的next指针指向原先的头节点。
- 第2步,把新节点变为链表的头节点。
& H z/ M$ |2 T# _
, R5 D/ m2 G3 k; |* z$ v( `3 n# Z2 e9 e, ~/ o$ d( S& G; C5 P
3.3. 中间插入中间插入,同样分为两个步骤。
- 第1步,新节点的next指针,指向插入位置的节点。
- 第2步,插入位置前置节点的next指针,指向新节点。8 f3 k8 o: ?& Z! Y8 g1 j* v: ^( r
% z7 l4 S K; b. [9 x
( _ h2 u2 Y/ r3 M: M' s
三钟情况的代码合到一起
8 J5 C a( ^! K7 d( [. _
2 g# t& e5 W; s/**( j3 J( ]8 P& }7 U
* 链表插入元素& N2 Y4 v' k$ {) o
*
' K/ m0 @- m3 A * @param index 插入位置
9 z9 _8 b0 d, E3 H; _ * @param data 插入元素 被插入的链表节点的数据
0 R4 D0 [+ i; m+ X6 T& o% ~ */. L: S5 n8 l* s
public void insert(int index, int data) {
# I% {6 T5 u2 k1 C/ E. j if (index < 0 || index > size) {( Z! U, N( e+ c8 W
throw new IndexOutOfBoundsException("超出链表节点范围!");
! H2 q" C; K2 ?- }, U# N0 O2 ~ }2 c% Q6 R R0 s# A
Node insertedNode = new Node(data);$ j& Y; ? p% [! _
if (size == 0) {
[9 O U; u) Y5 C- r+ x //空链表4 ]7 u7 Q: C3 `# N* F
head = insertedNode;
6 J# A* G9 b& {# b3 M7 j; k, \ last = insertedNode;
6 m* J% i2 [4 C I9 V% } } else if (index == 0) {
2 X$ N/ i+ z7 Z; m7 X/ q# p) j //插入头部* c$ O5 g# X7 l; w( A( A
insertedNode.next = head;
& s! N, e0 u) F* @ E" K9 `# z head = insertedNode;& e4 l* m; \( z( N( [
} else if (size == index) {2 }& S; d8 O( v- h, v
//插入尾部6 ], B1 P" ]4 c
last.next = insertedNode;
1 g2 U+ {7 {* d6 _ last = insertedNode;
6 x8 a. [. l& f" a2 i. W' t } else {% Z: i# E+ Z- u6 W: m# i
//插入中间
$ t0 O+ L0 B; ^1 t Node prvNode = get(index - 1);
' f% x! V8 r+ F: W insertedNode.next = prvNode.next;
! v2 t- N& g4 T" l- ^: | prvNode.next = insertedNode;
! Y. Y& Z) p4 H3 T* n3 o }7 [# G- ^: P2 q
size++;
: N, O. G% v0 P; S( ~ }
: q) h' |( a. R- w) N i R( N" Z2 T0 H% N, T4 [: g
/**1 N1 u! G1 |1 G; o: b! B
* 链表插入元素" f2 z$ }" r) N9 U% j4 u* B
*5 k) O% @4 a$ G* _ H1 ]
* @param index 插入位置
. M8 z/ N. ~; c% `* }) Y * @param data 插入元素 被插入的链表节点的数据/ y& `" k4 J; K3 }$ j5 q# l* W
*/: y5 \7 ?) u- T( G$ K9 I6 }; A T3 @
public void insert(int index, int data) {& \) a7 y% s1 h0 x( E( l$ L$ m$ W
if (index < 0 || index > size) {
3 a" Y; u$ T( R, |3 e+ j: ? throw new IndexOutOfBoundsException("超出链表节点范围!");
' ^2 v/ S! C( T. f# [5 ]8 e }
7 I8 |; d+ I8 d- o. L7 z Node insertedNode = new Node(data);2 t4 A$ R7 T* U- q
if (size == 0) {/ t: \+ J7 p0 q% n3 P
//空链表, G! A X0 n2 d6 j
head = insertedNode;
. ~) J! ~- e- `0 T0 v* @& s last = insertedNode;8 V$ c+ }0 t+ i4 u+ g# Q" A
} else if (index == 0) {
/ L v7 U, a) M. t0 K& U //插入头部
# }/ l' M, y8 F2 m# n insertedNode.next = head;: r% k: m5 x" d9 y
head = insertedNode;2 n! F7 A H( V4 N
} else if (size == index) {' `) M7 P7 P" C
//插入尾部+ D1 j' M" u! O
last.next = insertedNode;8 c6 K6 T% ^6 D, ]7 f( t+ Q% y: L
last = insertedNode;
3 `9 E# E; M7 I3 h3 ~7 X. w } else {
2 G {# K) a3 J" \1 T' i h$ E //插入中间
( |+ W2 M) u# P# J Node prvNode = get(index - 1);
2 {5 x6 n% s q. V insertedNode.next = prvNode.next;
- q8 H+ L) B: I9 m0 _ prvNode.next = insertedNode;& Y, p$ P& J, { p, G5 {+ `) c9 }
}+ b" w1 F9 S9 T& S3 X7 J8 t! F
size++;
5 u( r- b1 e2 S( E+ w" s }
; `; o% Q( H3 M8 j. f5 P4. 删除元素链表的删除操作同样分为3种情况。
- 尾部删除
- 头部删除
- 中间删除
) ~+ z! ~ t t2 M; k6 r
4.1. 尾部删除尾部删除,是最简单的情况,把倒数第2个节点的next指针指向空即2 M! z7 m& M9 z, L
可。
E6 E3 @2 r6 m* }
% I! A( H; n) m: R+ t* X
4.1. 头部删除头部删除,也很简单,把链表的头节点设为原先头节点的next指针即可。
6 M9 g* ^7 E; h1 Z. h3 v7 _$ W. u, L, T/ i- Y \7 K
4.1. 中间删除中间删除,同样很简单,把要删除节点的前置节点的next指针,指向要
8 w4 y( d/ [' h* Y" Z7 L删除元素的下一个节点即可。
5 }4 T/ `& q: P8 v
1 Y, \3 J" k6 M+ l9 b+ L4 S6 {! v C& J, c$ H& g" P
这里需要注意的是,许多高级语言,如Java,拥有自动化的垃圾回收机制,所以我们不用刻意去释放被删除的节点,只要没有外部引用指向它们,被删除的节点会被自动回收。
% E+ `, E' r. H3 r3 y3 F7 \如果不考虑插入、删除操作之前查找元素的过程,只考虑纯粹的插入和删除操作,时间复杂度都是O(1)2 w& d' x$ f: C: K' Z
/**
% U# c0 R6 w6 h: ?( H0 d * 链表删除元素& l3 |/ G' d$ r" T1 K, N3 ^
*
- \2 |; j& t. _; s# c5 g5 b * @param index 删除的位置
! P( |8 V( f5 j" O% {6 Y * @return 被删除的节点6 \; I6 w9 e/ d, N" C
*/# q! b a) G0 ~3 ^! ?! h1 Y/ f
public Node remove(int index) {
" V5 b& Y$ u" ]. g9 k4 a if (index < 0 || index > size) {" g) H4 o( u# i7 m2 g
throw new IndexOutOfBoundsException("超出链表节点范围");2 l9 o$ r) z$ R% [
}4 Y- v' z: F' c8 a1 m
Node removeNode;
; G8 @2 @8 @8 t" S if (index == 0) {
! O. T) k- q+ \8 F/ M8 s if (size == 0) {( f% B. @% ]& n5 }
throw new NullPointerException("当前链表为空,不可以进行删除操作");
2 H* A8 r M d W* |7 | }- o- m. v3 U0 l4 A/ d
//删除头节点 _4 ~+ g6 Y) \7 y/ p4 A& F) v
removeNode = head;* `( H' K! M [* m3 ?1 f
head = head.next;
) O9 m, {; V& v5 ~, y7 d8 O: t( w } else if (index == size - 1) {2 a% T) j& ^4 B; z/ r) n
//删除尾节点+ g3 ], m" q9 r$ c5 P
Node preNode = get(index - 1);
% ^" R/ q& \- L$ ^0 \ removeNode = preNode.next;
. S% \: H3 o% s7 X( M preNode.next = null;
% s: {5 v6 r2 O, V5 a/ K0 { last = preNode;1 l1 L3 E' n1 I/ `4 b
} else {6 ^9 K0 U+ z4 F
//删除中间节点
7 U3 W- H* N9 E1 w7 x Node prevNode = get(index - 1);* G! d. y9 c6 O
removeNode = prevNode.next;0 X9 C5 o; D2 t6 ~+ i7 H
prevNode.next = prevNode.next.next;' h& M; ~2 }7 O" S
}6 X5 T% J8 G8 Q9 e' {
size--;
) X$ l9 ?2 \7 s$ e. Y$ I3 _6 R; P return removeNode;# c( t) b& C% \4 t" p
}3 T/ R7 {; `5 O' T
Java实现链表的完整代码package chapter2.part2;
, l7 [& c7 F- A2 D( }- ]( u
4 `: _: Y# t+ g+ P' D; ^/**+ X6 m; o3 ?2 B- D9 |
* Created by IntelliJ IDEA.# _$ E1 ~% z) a# x3 y0 W# ~
*& e% a2 c& u7 k
* @Author: 张志浩 Zhang Zhihao3 x( R$ D$ f5 [1 t
* @Email: 3382885270@qq.com4 s5 g4 M7 y! T, t% `* f# c- R: V
* @Date: 2020/5/3
+ Z& d7 V; G7 I: A0 i# v5 Y * @Time: 13:39, R2 Z( d6 ]0 A: ~) R
* @Version: 1.0, h& F: w3 Q' D6 }( ^. s
*/, w' x& ^- q' ~2 v" p' P. I/ E: @7 I
public class MyLinkedList2 {
3 l% H* a0 o4 O& u private Node head; //头节点
K9 M! `0 D# R! B, J# P private Node last; //尾节点
8 U. A7 J# d( Q! c; k private int size; //链表实际长度: N. C+ v0 E- m8 n* q% a: p
: _; D& n* e M7 ] public static void main(String[] args) {
) f3 S( T q( D MyLinkedList2 myLinkedList = new MyLinkedList2();* e7 P+ Z# p9 B a: N, W' i
// myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空,不可以进行删除操作9 ]( b% d# }3 {% p( n Z: r
// myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围! z9 B m* I. ?. n: n; Q( b* U. u# h# m
myLinkedList.insert(0, 3);9 @+ n+ ^+ f1 l- ]' E: E& q" e9 f
myLinkedList.insert(1, 7);* h) a4 [* R) p; s! s, V- p8 ~
myLinkedList.insert(2, 9);* s" u7 Y9 Z5 h9 G
myLinkedList.insert(3, 5);0 G; b' t) X" ?& r9 M o n* c
myLinkedList.insert(1, 6);" |, V) V4 `5 i! D. c) T* k
myLinkedList.remove(0);
( s+ n' Q' Q5 c' W: @ myLinkedList.set(0, 23);' Q4 t- g- g3 L s
myLinkedList.output();
4 L/ f9 F3 i" d5 c$ N5 H- E# G }9 ?+ ~0 ~$ _3 ~6 S( \" V
) C$ b) r% t' B2 O5 l& y r: G% R
/**% C6 c, d$ a% ?' ]( P
* 链表插入元素
m( J7 Q7 U- m( K *
+ N! Q |# Z0 M, l * @param index 插入位置0 h5 @/ K7 }# e2 B1 R: G% `0 \
* @param data 插入元素 被插入的链表节点的数据
9 z% g* K; ?% M: q! r1 V0 T */- v4 ?; X5 R/ x+ `' p% z
public void insert(int index, int data) {# J6 p& p5 D6 ?) d1 Q
if (index < 0 || index > size) {- S* p5 J5 O- F1 q
throw new IndexOutOfBoundsException("超出链表节点范围!");2 }3 g {1 S$ V
}1 E/ \$ H; N' a& l. G1 ^
Node insertedNode = new Node(data);! a, F% ]- _ I
if (size == 0) {8 J* N m. y: W) m& o
//空链表
8 ~7 T2 z$ _' G# ?# e6 b head = insertedNode;
3 Y, V! L; t% V; T) g+ o last = insertedNode;1 D& P9 q" @) [& Y. x: L& V/ L" N$ W
} else if (index == 0) {$ S4 r% |0 ?; d) t5 o6 @
//插入头部: n1 D% w+ b3 {- l0 C3 b4 X: v( h) q
insertedNode.next = head;# B8 A5 ? L* B$ J; K
head = insertedNode;# B5 u/ _8 w( M# w" h- z" l4 |
} else if (size == index) {
7 ~. g3 H q! w% U //插入尾部8 k) P, s7 |, c" @( p2 _0 p* V$ I
last.next = insertedNode;( ]! Z+ \ L! t- u# X$ H
last = insertedNode;
! N8 D* W- H0 Y8 @' B } else {
4 b ]/ O2 N( R$ K$ x l% f //插入中间6 @! r! R' `' {" f4 E
Node prvNode = get(index - 1);. i: B6 S' B- w- z( |5 H9 ?
insertedNode.next = prvNode.next;
/ ]) Y4 M' v0 p9 H+ f o prvNode.next = insertedNode;
% O3 F" L# \$ I; ^& D: r& L* o1 t }/ Y2 ~5 p- ?/ M
size++;
# S- O& @) `! d- | }
% {/ Z" ?0 C- w7 r$ `' d6 l* N. U/ J! X+ _, }
/**
( z8 e @ ]. t9 h# Y * 链表删除元素+ k, A$ X8 o+ u& T1 X! Y* Y
*
: _/ ~, }! e! f% F * @param index 删除的位置4 l7 V! f; y# X
* @return 被删除的节点
" @ C: z: {3 q; V( _. V7 t */9 {9 ^- b6 m' Q
public Node remove(int index) {
9 h1 t4 |) O8 M: K3 b* |1 T3 S6 Y8 ~: g if (index < 0 || index > size) {
& q- y! ?- k( V" I throw new IndexOutOfBoundsException("超出链表节点范围");
/ N. L3 C* K8 z2 f }
# {) ]1 T& `. C# _! C/ O4 ]' l$ e Node removeNode;! u: [' _# z! r; H( T
if (index == 0) {. N4 G c% ]! u
if (size == 0) {$ c+ O! e# l! s5 c
throw new NullPointerException("当前链表为空,不可以进行删除操作");
2 j/ y9 Y/ B1 L7 Q }
# M% t6 u9 B* v+ K g# D+ O //删除头节点
4 s j* V* Q' i removeNode = head;
3 s7 F( F8 p( C1 r+ `9 t' u head = head.next;% U2 k2 r2 E! Q$ }0 r# T' w
} else if (index == size - 1) {& J6 y+ m& M+ U% D0 {3 Z$ U
//删除尾节点( ?, B8 ?" E! P7 u% X
Node preNode = get(index - 1);/ l5 Y# `) J" R* L5 c, r s; `- P
removeNode = preNode.next;
' j- T2 F' T) E2 K* z: \ preNode.next = null;
# x1 Y% f; [& m3 D! H. | last = preNode;; `: g" x+ F- W6 M5 p
} else {
: c- Q1 T7 U7 t' V //删除中间节点$ D( V `1 P7 f9 ?6 k0 W: S5 I4 V
Node prevNode = get(index - 1);! v* I, Z0 }6 M1 Q4 Z
removeNode = prevNode.next;$ {1 j; X* u4 F% m! W0 o0 E" {
prevNode.next = prevNode.next.next;
' R$ D) z. T% J- E5 H# d! Y }
6 t' F" k+ b4 A& j- ?8 a size--;3 {% o8 D5 N2 T, i8 b
return removeNode;4 \% x/ V ?/ i! u2 q9 b/ r
}
5 Z: Q' H0 r# a) q. ]" a
/ A( Z4 @4 I- X, R6 _; e* f/ P; q, Q8 p /**
8 [3 x. r t; Y3 S4 U * 更新节点 将列表中指定位置的节点的data替换为指定的data。
$ u1 M }5 g; K" i *
$ r l5 z W- ^1 e * @param index 需要更新的节点的位置
$ n1 L- W) L+ z$ X5 t2 _& f * @param data 新data
5 T, Z4 x' }' ?; [% ?! N& x* s * @return 旧data, ?$ z- y& @; f3 [0 d2 y
*/
4 f" F$ W* o$ L public int set(int index, int data) {
6 e" T% }/ A+ [8 s Node x = get(index);
" M2 e6 D, | w int oldVal = x.data;+ ~1 a, X1 V* ~' c2 E
x.data = data;) k' ?8 l* ?* P4 G& D9 A
return oldVal;) u0 @5 {* ]- U& }) j- k# {& }
}7 p5 L7 q* W5 |2 U& z& @
( m) [- v0 P1 Y6 t/ _1 B6 } /**0 Y4 x4 y8 ]6 k: J6 l) d$ c
* 链表查找元素' G6 G* g' y3 `- n7 q8 g6 B, [! T
*
( c: l4 ?- Z% s" ?% U * @param index 查找的位置
6 Z$ i( G. W# l5 v+ p' h' e) Z * @return index位置的Node对象1 V2 T7 k3 p* x# q0 O
*/
1 @- R; H! V+ d3 r% [4 Z public Node get(int index) {
; z# V5 z7 r2 b: h if (index < 0 || index > size) {$ G. H+ l+ k* x/ @! z% I
throw new IndexOutOfBoundsException("超出链表的节点的范围!");
4 h) g- r9 U6 ^$ l9 ? }
$ z3 X1 X# C4 ]1 {* \: j6 J! G9 n Node temp = head;3 T: _; B5 p# X) v" \& A# }& y
for (int i = 0; i < index; i++) {- F% M: S* D- f: D4 m
temp = temp.next;
8 }* b- ]& M3 _7 L4 X }; D9 }2 B! L! K& A
return temp;
5 s3 [. `! {6 S# z- E! [& I }
$ G! S' R8 p* d0 x# y. I
3 b- y4 Q' m7 L2 l: i2 V /**' r J9 o/ }8 d, j
* 输出链表$ X r" P0 d. t- W( B8 j
*/. Z! R5 C2 C( J1 c: N+ y
public void output() {
# r+ `, J, o2 Q4 |4 q% d Node temp = head;( m4 H" U9 @2 P5 o% T* R* |# s! [
while (temp != null) {/ [ Z* A; j5 u; X' ^$ z. f3 b
System.out.print(temp.data + " ");, y9 u2 K% q: M ^( z$ ^
temp = temp.next;9 o: d0 Z: g& @1 K6 e% w& }* g0 p
}
* J( O( d/ _( d8 X9 c! [, L }( O( O+ O2 B. G5 O
$ q7 b0 o5 a$ ] /**
% d3 _3 |& F3 `0 `& P5 { * 链表节点
$ O- E2 \8 ]9 |, o */
2 Z6 _, @8 `9 e5 E class Node {% k# u1 s4 Y/ a0 Y+ _
int data;+ z; O$ T" J, ^: s. k, K5 d9 C, m' u' R
Node next;
. x" a- n. `! F; m1 l* f
, a9 ~ a6 x8 M. D9 N. Y. Y Node(int data) {/ m- M5 ]. r# G3 A; h l
this.data = data;
d. z3 k; d) j | }& ]/ \3 z: e7 W' K' o3 `
}
; D0 B6 Q7 ^$ T- L}' C& z& r$ i: {
/ s% m! w, M. T% Y3 r0 V
6 h+ y" Y6 O3 ]二、双向链表
/ K2 \! m; I) y
双向链表比单向链表稍微复杂一些,它的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev 指针。& s' f& Z. j, ?5 a
1 P- M' _$ t' T6 U. y* x" s7 I
( h" }2 ]3 X$ N
' R3 {$ u$ r5 c
: _0 P6 u( h* S$ A. v3 C! {; H————————————————- E# }3 r5 J8 F3 b7 z$ A- d4 R/ ~
版权声明:本文为CSDN博主「爱做梦的鱼」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
! ]/ s- b5 r/ t- {- ?6 G原文链接:https://blog.csdn.net/weixin_43124279/article/details/105904468
& G/ Y' f0 h; `% W
. P4 m8 c+ e, |6 t* O$ i
4 ]' z2 G& ]0 P+ i+ x% B$ P/ c
-
2.png
(256.36 KB, 下载次数: 239)
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |