-
Notifications
You must be signed in to change notification settings - Fork 1
/
linklist.html
executable file
·329 lines (309 loc) · 9.84 KB
/
linklist.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta content="text/html;charset=UTF-8" http-equiv="Content-Type"/>
<link rel="stylesheet" type="text/css" href="../tools/ctut.css"/>
<link type="text/css" rel="stylesheet" href="../tools/style.css"/>
<style type="text/css">@font-face {font-family: SHREE_BAN_OTF_0592;src: local("../tools/SHREE_BAN_OTF_0592"),url(../tools/SHREE0592.woff) format("opentype");</style>
<meta content="width=device-width,initial-scale=1" name="viewport"/>
<script src="../tools/jquery-1.10.2.min.js"></script>
<script>
aha = function(code) {
window.open("https://rdrr.io/snippets/embed/?code="+code)
}
togglePhoto = function(photoId) {
var me = document.getElementById("pic_"+photoId)
if(me.style.display=="block"){
me.style.display="none";
}
else if (me.style.display=="none"){
me.style.display="block";
}
}
hideShow = function(lb) {
var me = document.getElementById(lb)
if(me.style.display=="block"){
me.style.display="none";
}
else if (me.style.display=="none"){
me.style.display="block";
}
}
grabData = function(data){
return "https://farm"+data.photo.farm+".staticflickr.com/"+data.photo.server+"/"+data.photo.id+"_"+
data.photo.secret+".jpg"
}
fromFlickr = function(photoId) {
$.getJSON("https://api.flickr.com/services/rest/?method=flickr.photos.getInfo&api_key=23a138c73bdbe1e68601aa7866924e62&user_id=109924623@N07&photo_id="+photoId+"&lang=en-us&format=json&jsoncallback=?",
function(data) {
imgURL = grabData(data)
var l = document.getElementById("lnk_"+photoId)
l.href = "https://www.flickr.com/photos/109924623@N07/"+photoId
var i = document.getElementById("pic_"+photoId)
i.src=imgURL
i. {
document.getElementById("status_"+photoId).innerHTML="[Image loaded. Click to show/hide.]"
}
})
}
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js","color.js"],
jax: ["input/TeX","output/HTML-CSS"],
tex2jax: {inlineMath: [["$","$"],["\\(","\\)"]]},
TeX: {
Macros: {
h: ["{\\hat #1}",1],
b: ["{\\overline #1}", 1],
row: "{\\mathcal R}",
col: "{\\mathcal C}",
nul: "{\\mathcal N}"
}
}
});
</script><script type="text/javascript" src="https://www.isical.ac.in/~arnabc/MathJax/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script><script type="text/javascript" src="../MathJax/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script><script src="../tools/htmlwidgets.js"></script>
<link href="../tools/rgl.css" rel="stylesheet"></link>
<script src="../tools/rglClass.src.js"></script>
<script src="../tools/CanvasMatrix.src.js"></script>
<script src="../tools/rglWebGL.js"></script>
</head>
<body>
<a href="http://www.isical.ac.in/~arnabc/">[Home]</a>
<h3>Table of contents</h3>
<ul>
<li>
<a href="#Linked lists">Linked lists</a>
</li>
<li>
<a href="#Insertion">Insertion</a>
</li>
<li>
<a href="#Deletion">Deletion</a>
</li>
<li>
<a href="#Implementing in C">Implementing in C</a>
</li>
</ul>
<hr/>
<h1><a
name="Linked lists">Linked lists</a></h1>
Suppose that I have a list of my friends on a piece of paper:
<pre>
Samprit
Atanu
Jonaki
Krishanu
Saikat
</pre>
The order is important, the first friend is the closest, the
next one the second closest, and so on. After writing the list up
to this, I suddenly recall that I have missed a name: Anvit. He
should be third in the list. Unfortunately, as I am writing on a
piece of paper, inserting a name between two names is difficult
(unless I use ugly scribbling). However, if my list were in a
computer, then it is very easy: I would just take my cursor after
Atanu, hit enter to create a black line (causing the everything
below to shift downwards by a line), and then type Anvit in the
blank line. In this way I can insert as many names as I wish in
any position. No scribbling, no squeezing. I might even remove
any number of names from the list, without leaving any ugly
gap. The list just grows,
stretches and shrinks as needed.
<p></p>
How does the computer manage this? Does it reserve lots of empty
spaces between every pair of names, to allow for future
insertions, and somehoow hide the spaces while displaying the
list? Not really. It uses a clever trick called a <b>linked
list</b>, which we shall discuss now.
<h2><a
name="Insertion">Insertion</a></h2>
When we make a list on paper, adding a new name is easy, as long
as you are adding it at the end. Well, internally the computer is
also writing the names on just such a piece of paper. This paper
has lines drawn on it, and every line is numbered. Thus, the
paper looks like this:
<pre>
1 Samprit
2 Atanu
3 Jonaki
4 Krishanu
5 Saikat
6
7
8
9
...
</pre>
Unlike our paper list, the computer also writes after each name
the number of the line where the next friend is to be found:
<pre>
1 Samprit 2
2 Atanu 3
3 Jonaki 4
4 Krishanu 5
5 Saikat 0
6
7
8
9
...
</pre>
The 0 after Saikat means that Saikat is the last name in the
list. Nothing interesting so far. Now suppose that I need to
insert Anvit in the third position. The computer simply writes
Anvit at the next available position:
<pre>
1 Samprit 2
2 Atanu 3
3 Jonaki 4
4 Krishanu 5
5 Saikat 0
6 Anvit
7
8
9
...
</pre>
I want Anvit to appear after Atanu. So I write 6 after Atanu.
Similarly, Jonaki should appear after
Anvit. So I write 3 after Anvit:
<pre>
1 Samprit 2
2 Atanu <font color="#ff0000">6</font>
3 Jonaki 4
4 Krishanu 5
5 Saikat 0
6 Anvit <font color="#ff0000">3</font>
7
8
9
...
</pre>
Is this clear. Then try these exercises.
<p>
<b>EXERCISE:</b>
Insert the name Arko after Krishanu.
Next, insert the name Oishi <i>before</i> Saikat.
<img src="../image/box.png"></p>
<p>
<b>EXERCISE:</b>
Which is more difficult:
inserting <i>after</i> a given name, or <i>before</i> a given
name? Will the difficulty increase if the list is very long?
<img src="../image/box.png"></p>
<p>
<b>EXERCISE:</b>
Add Subroto after Saikat. Thus, Subroto is now the last in the list.
<img src="../image/box.png"></p>
Now suppose I suddenly find a long lost friend, Arinjita, and
must give her the first place. So I need to update the list as
follows.
<pre>
1 Samprit 2
2 Atanu 6
3 Jonaki 4
4 Krishanu 5
5 Saikat 0
6 Anvit 3
7 Arinjita 1
8
9
...
</pre>
But here you'll have a problem while displaying the list. We have
to start from Arinjita (<i>i.e.</i>, line 7) and not from line 1. How on
earth are we to know where to start from? The computer needs to keep track of that separately. It
calls the line number corresponding to the first name
the <b>head</b>. So far, the head was always 1. But after
inserting Arinjita, the head changes to 7. Henceforth, we shall
denote the head with a star:
<pre>
1 Samprit 2
2 Atanu 6
3 Jonaki 4
4 Krishanu 5
5 Saikat 0
6 Anvit 3
*7 Arinjita 1
8
9
...
</pre>
<h2><a
name="Deletion">Deletion</a></h2>
We talked about inserting a name in the list. Deleting is even
easier. Suppose that we want to delete the name after line number
2. The next line number is 6 (Anvit), and after that comes line 3
(Jonaki). Our aim is to delete Anvit from the list, <i>i.e.</i>, we
should have Jonaki coming right after Atanu. Convince yourself
that the following updating achieves this:
<pre>
1 Samprit 2
2 Atanu <font color="#ff0000">3</font>
3 Jonaki 4
4 Krishanu 5
5 Saikat 0
6 Anvit 3
*7 Arinjita 1
8
9
...
</pre>
Notice that we do not need to do anything to line 6. Just by
making sure that line 6 is not referred by others, we are
effectively removing Anvit from the list.
<p>
<b>EXERCISE:</b>
Delete the head from the list, <i>i.e.</i>, delete Arinjita making the
next guy, Samprit the new head.
<img src="../image/box.png"></p>
<h2><a
name="Implementing in C">Implementing in C</a></h2>
As the discussion above shows, the computer maintains a secret paper
list (which can only grow), and displays the final list cleverly
by following the next line numbers. Well, as you might have
guessed, there is really no paper list inside a computer. The
role of the paper is played by the memory of the computer. This
memory is indeed like a long (very l..o..n..g) piece of papers
with many lines marked on it. Just as in our example, the lines
are numbered consecutively. Each lines is
called a <b>location</b> and its number is called
its <b>address</b>. As there are a huge number of locations, the
address easily runs into 20 digits or so!
<p></p>
Now, we need to associate a location with an address. There has
to to be a 2-way communication: address to location, and location
to address. If you have a variable <font color="red"><code>x</code></font> stored at some
location, then its address is given by <font color="red"><code>&x</code></font>. Conversely, if
the address of a location is stored in a variable
called <font color="red"><code>p</code></font>, then the corresponding location
is <font color="red"><code>*p</code></font>. Incidentally, just as integers are stored
in <font color="red"><code>int</code></font>'s and characters in <font color="red"><code>char</code></font>'s, there are
special types of variables to hold addresses
called <b>pointer</b>s.
<p></p>
Thus, to store a name and the address of the next student we need
a string and a pointer. Typically, you package them as follows in
C:
<span class="j">
<pre>
struct <font color="#ff0000">stdnt</font> {
char <font color="#ff0000">name</font>[80];
struct <font color="#0000ff">stdnt</font> *<font color="#ff0000">next</font>;
}
</pre>
</span>
Yes, it is ugly. Nobody denies that. But that is how it is in
C. Here the red words are words of our choice. The black words
are parts of the C language. The word <font color="red"><code>stdnt</code></font> has occurred
twice (the second occurrence is shown in blue).
<hr/>
<table width="100%" border="0">
<tr>
<td align="left"/>
<td align="right"/>
</tr>
</table>
<hr/>
</body>
</html>