CS211 - Algorithms and Data Structures II
Tutorial 6
T Naughton, CS NUIM
Back to CS211 home
This is a tutorial on linked lists.
Problems 6.2, T6.1
Problem 6.2 A class to maintain an ordered linked list of integers is required. Integers are to be sorted in ascending order. Call your class OrdIntList. The following methods should be supported by your class:
OrdIntList::Add // Add an integer to the list at an appropriate position
OrdIntList::PrintList // Print out the contents of the list
OrdIntList::Contains // Return true/false if an integer is in the list
This problem is very similar to previous problems except, as explained in the last lecture, your Add() method must determine which position in the list to add the new node.
There is no need for any user interaction. Use main() to test your program. An example of one such main() is shown below (text version here).
void main(void){
OrdIntList list; // the ordered list
int tempint; // temporary storage
list.Add(5);
list.Add(2);
list.Add(9);
list.PrintList();
tempint = 99;
cout << endl << tempint << " is ";
if (!list.Contains(tempint)) {
cout << "not ";
}
cout << "in the list.";
tempint = 9;
cout << endl << tempint << " is ";
if (!list.Contains(tempint)) {
cout << "not ";
}
cout << "in the list.";
}
Problem T6.1 There are many ways of printing out a singly-linked list in reverse order. Outline how to solve the problem using each of the following techniques:
- Push onto a linked list stack and then pop (thanks Dave C) [requires O(n) space resources and O(n) time resources]
- Copy the linked list into a dynamically allocated fixed-size array and print out the array in reverse [requires O(n) space resources and O(n) time resources]
- Iteration using the list size and a counter to print out the nth element, followed by the (n-1)th, etc. [requires O(1) space resources and O(n2) time resources]
- Iteration using a circularly-linked list and the list size [requires O(1) space resources and O(n2) time resources]
- Change to a doubly-linked list to allow traversal in both directions [requires O(1) space resources and O(n) time resources -- is this cheating (changing the problem statement)?]
- Recursion with a pointer to the next element in the list [requires O(1) space resources and O(n) time resources -- neatest solution, however our model of computation does not take into account the time and space overheads associated with implementing a recursive call]
These techniques will require the use of the following methods:
Add an element to the front of the list
Count the number of elements in the list
Return the nth integer in the list (if the list has >n elements)
Return a pointer to the node that appears n nodes after the currently pointed to node
Further Problems: Linked list functionality that may be required in the future:
- Return the location of the first instance of integer X in the list (if it is in the list)
- Return the locations of the first two duplicates found in the list
- Remove any duplicates from the list
- Swap any occurances of integer X in the list with integer Y
- Remove all integers less than X from the list
- Find the average value of the integers in the list
- Normalise the contents of a list of doubles (divide every element by the highest value in the list)