We'll study another data storage structure that solves some of the problems caused by arrays: linked list. Linked lists are probably the 2 nd most commonly used general purpose storage structures after arrays. Please compare the strengths and weaknesses between arrays and linked list while we go along.
At the end of this lab, you need to submit a word document including some text answers and screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs->Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).
To execute an applet in Internet Explorer, perform the following steps.
(1.) Click Start > Windows System -> Command Prompt
(2.) Use command "cd" to move into the directory where you run the applet, such as cd C:\COSC3331\Chap05\LinkList
(3.) Open the applet by typing "appletviewer LinkList.html".
(4.) Enter 10 in Number, and click New to create a10-element linked-list for Figure 1, the computer will randomly initialize some values between [1, 1000].
Fig. 1 Initial State for a 10-Element Unsorted Linked List see image.
(5.) Fill-in Number and click Ins to insert some numbers in sequence of 5, 551, 123, 47, and 182, then we have Figure 2. Q1: Which end it uses to insert? Front(red arrow) or Tail (last element)? Why not the other end?
Fig 2 State of Unsorted Linked List after Some Insertions see image.
(6.) Enter 5 in Number and click Find to search 5, see Figure 3. Q2: When searches any unavailable element (such as 15), how could it decide it is not in the linked list?
Fig 3 State of Unsorted Linked List after Find the Element 5 see image.
(7.) Enter 5 in Number and click Del to remove 5, we have Figure 4 after deletion. Q3: What is the operation process for that process, describe it? How about the duplicate elements on the same value? Exercise it by yourself.
Fig 4 State of Unsorted Linked List after Delete the Element 5 see image.
(1.) Enter 10 in Number, and click New to create a10-element linked-list, at this time we select option Sorted for a sorted linked list, see Figure 5.
Fig. 5 Initial State for a 10-Element Sorted Linked List see image.
(2.) Use Number and click Ins to insert some numbers in sequence of 5, 551, 123, 47, and 182, then we have Figure 6. Q4: What is the difference with Unsorted Linked List at insertion operations?
Fig 6 State of Sorted Linked List after Some Insertions see image.
(3.) Enter 551 in Number and click Find to search 551, we have Figure 7 after we find it. Q5: It seems that it is ordered, so could we use the binary search instead of the linear search we used here? (Hint: we must have access for any element if we use binary search.)
Fig 7 State of Sorted Linked List after Find the Element 551 see image.
(4.) Enter 551 in Number and click Del to remove 551. In Figure 8 there is no 551 in the sorted linked list, try to click Del again. Q6: What is the difference with Unsorted Linked List at deletion operations to confirm the element is not in the list?
Fig 8 State of Sorted Linked List after Delete the Element 551 see image.
Q1: Which end it uses to insert? Front or Tail? Why not the other end?
Q2: When searches any unavailable element (such as 15), how could it decide it is not in the linked list?
Q3: What is the operation process for that, describe it? How about the duplicate elements on the same value? Exercise it by yourself.
Q4: What is the difference with Unsorted Linked List at insertion operations?
Q5: It seems that it is ordered, so could we use the binary search instead of the linear search we used here? (Hint: we must have access for any element if we use binary search.)
Q6: What is the difference with Unsorted Linked List at deletion operations to confirm the element is not in the list?
Submit the screenshots for Figures 2, 3, 4, 6, 7, and 8 (totally 6 figures) through Blackboard. (Don't forget to include your name in the program). (At the end of this lab, you need to submit a word document including some screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs- >Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).