ISBN13: 9781449646752 C++ Plus Data Structures 5th Edition Chapter 6 Question 12

Question

ISBN13: 9781449646752 C++ Plus Data Structures 5th Edition

Chapter 6

Question 12

Of the three variations of linked lists (circular, with head and trailer nodes, and doubly linked), which would be most appropriate for each of the following applications?

A. You want to search a list for a key and return the keys of the two elements that come before it and the keys of the two elements that come after it.

B. A text file contains integer elements, one per line, sorted from smallest to largest. You must read the values from the file and create a sorted linked list containing the values.

C. A list is short and frequently becomes empty. You want a list that is optimal for inserting an element into the empty list and deleting the last element from the list.

Explanation / Answer

Special Linked Lists

Introduction ( to Special Linked Lists):

In this lecture we will cover some standard variations of simple linear-linked

lists: circular, header, trailer, and doubly-linked lists. We will discuss the

tradeoffs between using these lists and simple linear-linked lists.

Circular Lists:

Standard linearly-linked list are used more often than any of these variants,

but it is interesting to see what tradeoffs the variants allow. The web reading

discusses these special lists in more detail. It would be an excellent idea to

hand simulate the methods there to become more familiar with how these special

lists are processed.

In "circular lists", the "rear" node doesn't store null in its .next field,

but instead has its .next field refer to the "front" node in the list. I put

"rear" and "front" in quotes because in a circular list, there really is not

an obvious front or rear node (unless we have a special reference into the

list named front or rear).

There are a few applications for circular lists. One allows us to represent

and efficiently process a queue by having a single reference to the "rear"

value in the queue (instead of one to the front and one to the rear). Note that

in a circular list, the node one beyond the rear is the front, so both the

front and rear nodes in a queue are easily reached from the rear node (and all

"action" in a queue is at the front/remove or end/add).

If rear refers to the last node an a queue represented by a circular list,

here is code to add to the rear of the queue. Draw a picture of an empty

list, a list with one node, and a list with 3-5 nodes and simulate this

code on those lists to see that it is correct.

if (rear != null)

    rear = rear.next = new LN(someValue,rear.next);

else

    rear = new LN(someValue,null);

    rear.next = rear;               //Make it a 1 node circular list

}

If rear refers to the last node an a queue represented by a circular list,

here is code to remove the front of the queue. Draw a picture of an empty

list, a list with one node, and a list with 3-5 nodes and simulate this

code on those lists to see that it is correct.

if (rear != null) {

    int frontValue = rear.next.value;

    if (rear.next == rear)             //Just 1 node in the list?

      rear = null;

    else

      rear.next = rear.next.next;

}

If we had to represent a huge number of queues, most of which are empty,

using a class that stored one reference to the rear of a circular list will

save space when compared to using a class that stores two references to the

front and rear of a linear-linked list.

Header Lists:

In "header lists", every list has a special (valueless) header node at the

front. So, an "emtpy header list" would have one list node on it. All "real"

nodes in the list come after the header. By using a header node, special cases

in the code are reduced. For example, I wrote the following code for adding a

value to the end of a linked list, in a class with front and rear instance

variables.

    if (front == null)

       front = rear = new ListNode(e,null);

    else

       rear = rear.next = new ListNode(e,null);

If the linked list were a header list, if it were empty the front and rear

would both be set to the header node (whose .next is set to null in the

constructor). We could remove the special case above (front is never null) and

simplify the code to the if-less

    rear = rear.next = new ListNode(e,null);

In a header list, one never changes front: it always refers to the header.

So every node we manipulate in the list has a previous node referring to it.

This simplifies the code for adding and removing nodes, although for other

operations (like traversal) we must remember to skip the header node.

Trailer Lists:

In "trailer lists", every list has a special (valueless) trailer node at the

end. So, an "emtpy trailer list" would have one list node on it. All "real"

nodes in the list come before the trailer. By using a trailer node, we can

remove a node that we have a reference to, without having a reference to the

node before it!

I'll show this "trick" in class; hand simulate the following code again to see

how it works (have r refer to the first, last and middle node in a trailer

list). Note that the "last" node IN a trailer list is the one before the

trailer node. This code works correctly only if the node r refers to is

followed by another node (which is guaranteed for a trailer list; and r -the

node to be removed- will never refer to the trailer itself).

    r.value = r.next.value;

    r.next = r.next.next;

Doubly-Linked Lists:

In "doubly linked lists", each node refers to the one after it and the one

before it. So, we can traverse the list in both directions: we can reach any

node from any other node. The cost is an increase of space needed to store a

doubly-linked list: twice as many references in each node (2 instead of 1) and

the requirement to change twice as many references when we mutate the list,

e.g., when adding/removing values.

For example, when we add a node to a doubly linked list, we need to make

the .next of the one before it refer to the new node, and the .previous of

the one after it refer to the new node. And in the new node itself, we need

to set its .next as well as its .previous instance variables

If the node added is at the front or rear of a doubly linked list, there are

all sorts of special cases to handle. By having both a header and a trailer

node in a doubly linked list, we can simplify this code and remove all the

special cases. But now, even an empty list has two nodes: the header/trailer.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.