CS210 - Algorithms and Data Structures I Department of Computer Science National University of Ireland, Maynooth

T Naughton, NUIM
Back to CS210 home

Laboratory Sheet 9

Dynamic data structures: the linked list In this lab you will implement a linked list data structure. Answer Problems 9.1 and 9.2.

When you are finished, get a head start revising (array-based implementations of stacks/queues/sets and complexity analysis) for Lab Exam 2.

Here are some sorting algorithm simulators to prepare you for next week's lecture (at the website of Goodrich's & Tamassia's textbook).

Important! Your lab book will be collected at the beginning of your lab exam next week. Make sure to bring it with you.

A linked list class

A version of the Node class, constructed during the last lecture, has been modified to hold Objects rather than ints. It now becomes part of the MyLinkedList class that implements a linked list ADT. MyLinkedList includes methods to add/remove elements and print the list. Here is a simple tester program.

Problem 9.1 Use the linked list class to implement a stack data structure. This will be very similar to the array-based inplementation of a stack given in lectures, except you will have a MyLinkedList data structure instead of an array.

Problem 9.2 Modify the MyLinkedList class by adding a new method addToBack(). Use this modified linked list class to implement a queue data structure.

Problem 9.3 (homework) Create a new new class MySortedLinkedList that extends MyLinkedList and keeps its list of items sorted in ascending order (you will need a new type of add() method).