[Solved] Assignment 4 – Lists

Write pseudo-code not Java for problems requiring code. You are responsible for the appropriate level of detail.

The questions in this assignment give you the opportunity to play with simple lists, then explore a new data structure and to experiment with the hybrid implementation in Q6.

1. Write an algorithm to reverse a singly linked list, so that the last element become the first and so on. Do NOT use Deletion – rearrange the pointers.
2. What is the average number of nodes accessed in search for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array? Note that a list could be implemented as a linked structure or within an array.
3. Write a routine to interchange the mth and nth elements of a singly-linked list. You must rearrange the pointers, not simply swap the contents.
4. A deque (pronounced deck) is an ordered set of items from which items may be deleted at either end and into which items may be inserted at either end. Call the two ends left and right. This is an access-restricted structure since no insertions or deletions can happen other than at the ends. Implement the deque as a doubly-linked list (not circular, no header). Write InsertLeft and DeleteRight.
5. Implement a deque from problem 1 as a doubly-linked circular list with a header. Write InsertRight and DeleteLeft.
6. Write a set of routines for implementing several stacks and queues within a single array.

Hint: Look at the lecture material on the hybrid implementation.