Transcript Sorted Linked List

Sorted Linked List
A linked list is a data structure that consists of a sequence of data
records such that in each record there is a field that contains a reference
(i.e., a link) to the next record in the sequence.
Course Name: Networking
 Author(s) : Phani Swathi Chitta
Mentor: Aruna Adil

Level(UG/PG): UG
*The contents in this ppt are licensed under Creative Commons Attribution-NonCommercial-ShareAlike 2.5 India license
Learning Objectives
After interacting with this Learning Object, the learner will be able to:
• Explain the concept of sorted linked list
Definitions of the components/Keywords:
1
2
Glossary:
• Node: Node contains a value and reference to next node
• Reference: Reference is address of next node in the linked list
• Null Pointer: Reference with no address
• Head: Starting node of linked list
3
4
5
• TEMP node: Node with no address
Definitions of the components/Keywords:
1
2
3
4
5
In Computer Science, a linked list is a data structure that
consists of a sequence of data records such that in each record
there is a field that contains a reference (i.e., a link) to the next
record in the sequence.
Linked Lists are among the simplest and most common data
structures. They provide an easy implementation for several
important abstract data structures including stacks, queues, hash
table, symbolic expressions and skip lists.
The principle benefit of a linked list over a conventional array is
that the order of the linked items may be different from the order in
which the data items are stored in memory or on disk. For that
reason, linked lists allow insertion and removal of nodes at any point
in the list, with a constant number of operations.
Master Layout 1
1
Sorted Linked list:
2
Fig. A
Fig. B
3
4
5
• Give a PLAY button
• Give PAUSE and RESTART/CLEAR buttons
• Give the color details as given below
1
Step 1:
Sequence: 15, 50, 40, 10, 60, 35
2
3
4
Instruction for the animator
• When the user clicks PLAY, show fig. A in
the master layout along with the sequence
given above
• The text in DT should appear in parallel to
the figure
5
Text to be displayed in the working area (DT)
• Now new TEMP node is 15. It is inserted in sorted linked list at position 1.
1
Step 2:
2
3
Instruction for the animator
4
• The next number in the sequence should
appear in the TEMP node square box and
the linked list square box.
• Place the new number at proper position
depending on the value greater or less
than the numbers present in the linked list.
• Finally all the numbers in the sorted linked
list must be in the ascending order.
5
• In the sorted linked list, give the box blue
color and the next section in pink color.
• The text in DT should appear in parallel to
the figure
Text to be displayed in the working area (DT)
• Now new TEMP node is 50. It is inserted in sorted linked list at position 2
as value of TEMP node, 50 is greater than 15.
1
Step 3:
2
3
4
Instruction for the animator
• The similar process given in the previous
slide follows till the end of the sequence
• The text in DT should appear in parallel to
the figure
5
Text to be displayed in the working area (DT)
• The value of TEMP node is 40. As it is greater than 15 but less than 50, it
comes at position number 2 in the sorted linked list.
1
Step 4:
2
3
4
Instruction for the animator
• The similar process given in the slide 2 is
followed till the end of the sequence
• The text in DT should appear in parallel to
the figure
5
Text to be displayed in the working area (DT)
• Now new TEMP node is 10. It is inserted in sorted linked list at position 1 as
value of TEMP node, 10 is less than 15.
1
Step 5:
2
3
4
Instruction for the animator
• The similar process given in the slide 2 is
followed till the end of the sequence
• The text in DT should appear in parallel to
the figure
5
Text to be displayed in the working area (DT)
• Now new TEMP node is 60. It is inserted in sorted linked list at position 5 as
its value 60 is greater than 50.
1
Step 6:
2
3
4
Instruction for the animator
• The similar process given in the slide 2 is
followed till the end of the sequence
• The text in DT should appear in parallel to
the figure
5
Text to be displayed in the working area (DT)
• The value of TEMP node is 35. As it is greater than 15 but less than 40, it
comes at position number 3 in the sorted linked list.
Electrical Engineering
Slide
1
Introduction
Slide
3
Definitions
Slide
13-17
Analogy
Slide
18
Want to know more…
Test your understanding
Lets Sum up (summary)
(Further Reading)
(questionnaire)
Interactivity:
•The same algorithm as in demo is
followed
• When ADD is selected, add the
values given by user and fill the sorted
linked list.
• When REMOVE is selected, remove
the particular number from the list as
given by user
• When SEARCH is selected, find out
the corresponding number in the list
Try it yourself
• Give a text box to enter
node value
• Give limit that only 7
nodes can be added
• Give ADD, REMOVE and
SEARCH buttons
12
Credits
Questionnaire
1
2
1. In the sorted linked list with n elements, how many shift
operations are required for deleting the first element?
Answers:
3
a) n
b) 0
c) n-1
4
5
d) n/2
Questionnaire
1
2
2. Suppose getFront is called on a sorted linked list that has
exactly two entries with equal priority. How is the return
value of getFront selected?
Answers:
3
a) The one is chosen at random
b) The one which was inserted first
c) The one which was inserted most recently
4
5
d) This can never happen (violates the precondition)
1
2
Questionnaire
3. An array of Linked List can be used to implement a Sorted
Linked List, with each possible priority corresponding to its
own element in the array. When is this implementation not
feasible?
A. When the number of possible priorities is huge
B. When the number of possible priorities is small
3
Answers:
a) Both A & B
4
b) Only A
c) Only B
d) None
5
Questionnaire
1
2
4. Suppose temp points to a node in a Linked List, what
Boolean expression will be true when cursor points to the
tail node of the list?
Answers:
3
a) cursor==null
b) cursor->next==null
c) cursor->next==null
4
5
Questionnaire
1
2
5. Suppose that TEMP is a pointer variable that contains the
NULL pointer. What happens if your program tries to read or
write *TEMP?
Answers:
3
a) A syntax error always occurs at compilation time
b) A run-time error always occurs when *TEMP is evaluated
c) A run-time error always occurs when the program finishes
4
5
d) The results are unpredictable
Links for further reading
Reference websites:
http://en.wikipedia.org/wiki/Linked_list
Books: