Data Structures and Algorithms
Mohammad GANJTABESH
Department of Computer Science,
School of Mathematics, Statistics and Computer Science,
University of Tehran,
Tehran, Iran.
[email protected]
Dept. of Computer Science
University of Tehran
Linked List
Data Structures and Algorithms
Undergraduate course
Mohammad GANJTABESH Dept. of Computer Science
[email protected] University of Tehran
int A 153 § Memory
Alo ] = Li Code
A. [I] s 2
'
"
, Pata
int * Bi
size flint )) :
B- Lint ) make ( 5 *
◦
*
Bk ] = Ii = * B =L 's
• " " * i.
Memoir
""
^
izs¥
i ☐: "
Y:&
mmmm
6/5
?⃝
Boundary Conditions
s
S 's i-wu.1.CH -1
OH a' v.i. f- 2 Data
did × 64¥61 -3
/
I - I
✓
-61 it 6%1%1-4
ius ab
- • a > Is it ,
> 0¥ -5
1 / 11
Basics
I # * → # • * yolk #± ±
-
I % % v4 % ?
4 ÉF→☒
Head
struct Node {
Node
int Data
FEET
:
Node * neat ;
Block for
3 Building
linked List .
2 / 11
Linked List :
/
""" " " "
class Linked list { First (5) ;
( •
Add
Node * head 's
L . Add First (lo ) :
int size 's
[ .
Add First (207 :
team
Linked list 1) { sized
tf
head _- null ;
tread
size
☒→Ñ
=
} size -2
head
11 other methods
,☒→1→T
} size =3
mmmm
6/5
Linked List: Add an element at the beginning
it LL is
§
void Add First ( int a) {
empty
"" " "" "" " " "" "
&tf " ""
node •
next → head ;
-
head & node
¥ad
= 's
size + + ;
} *
Array
-
:
rig .
Ijf new
Td
Node
②
3-
061 ✗
3 / 11
Linked List: Add an element at the end
if LL is empty :
void Add Last (a) {
Node node = new Node (a) i
d¥
(
¥ "
Node
" " ""
" " " new
" "" " " " " "
head = & node ;
size
return
++
;
s "
#
""
% .ae temp neaa *,
t≠
. ,
while (
temp neat .
! -
null )
temp =
temp next ; .
temp next tf
1js
• = & node :
size + +
}
4 / 11
Linked List: Efficient AddLast operation
Linked List {
[☒-☒
.
Class
Node * head :
Node * tail ;
int
i
sire ;
☐ˢ31
}
n•idAddLast(intx)#
*
tail
☐ 0£
tf
new
Node
n.aen.ae.n.ua .
/
if ( head snail )t
head tails & node ;
size + + i
return ,
}
tail next
. = & node :
tail = & node ;
size → + ;
} 5 / 11
Linked List: Remove an element from the beginning
•innemidd③
Boundary conditions Remove First 1) {
|
int
:
K" ) :
F
1) Empty if (head null ) return
2) single element
int data head Data 's
3)
working at begin = .
4) x r end
if ( head - → tail )
head tail null ;
I
= =
if LL is empty else
☒i
head
① ±%
head = head .
next ;
"" "
"
return ( data) ;
El
,
+¥
6 / 11
int
Linked List: Remove an element from the end
Remove last C) { ① head
conditi
Boundary
)
if ( head null ) return
= -
Gull
if
:
int data tail Data ;
FF
= .
ifl head tail )t
head tail → null 's size -
-
;
THE
-
return ( data ) ;
}
else }
Node current head ;
o:÷=
☐ 1y
* =
/
Node * previous s null ;
while ( current ! -
tail)t
me " " " = " " ent
" "
neat ;
F1☒#
current = current •
}
previous newt = null
f
.
tail previous 's Previous
fumed
=
, size -
; return ( data ) 's
7 / 11
?⃝
Linked List: Remove a specific head
element
previous
Remove ( int {
Ez ↓
int a)
Node * current = heads
Node null
* previous =
's
current TF
while ( current
if ( current
1. = null ) { # Dis
. Data → a) {
if( current head )
( Remove First (1) ;
tail
return
if ( current tail )
return ( Remove
Lasta ) ;
size 3
current next ;
- -
previout next . = -
return
} ( current Data ) ; .
Previous =
current ;
current current nent ;
} = .
return ( null ) ;
} 8 / 11
Linked List: Access to the first/last element
int Peek Firstly je
if ( head return ( null ) ; ☒
)
→
= - null
return ( head -
Data ) ;
} 1€
int peek Last C) {
I
☒
if /
return
tail =
( tail
- null
.
)
Data )
return
;
( null ? ,
I
} D
*.
9 / 11
Linked List: Find a specific element
b. l•
Node
contains
*
(
tmp
int
=
a)
head
{
;
µatmˢ
¥
while (
tmp
ifltmp •
1.
Data
= null
-
)}
- x )
}
return (true ) ;
t
tmp newts
tmp = -
t☒
} ☐
tart
return (false ) ;
10 / 11
Linked List: Other operations
is Empty 1)
Before ( int int key)
Add n
,
int
Add After ( int n , key )
Reverse C)
Range ( int )
Linked List min ,
int man
I.
11 / 11
of linked list
Type :
Linked list discussed
D single
I .
Linked List
2) Doubly
Nod
head Data*wt
F →←☒i→←☒
3) Circular Linked List : tail
head
i→→☒→☐→D"
'+
4) Circular Doubly Linked List
€s→☒i mmmm
6/5
Linked list us .
Array
✓
Random Access ✗
✓
Cache Friendly ✗
✓ ✓
Sequential Access
✓
Ease of use ✗
Fit the size ✓ ✗
required
✓
memory usage ✗
✗
Dynamicity ✓
