ISBN13: 9781449646752 C++ Plus Data Structures 5th Edition chapter 3 The specifi

Question

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

chapter 3

The specifications for the Unsorted List ADT state the item to be deleted is in the list.

1) rewrite the specification for DeleteItem so that the list is unchanged if item to be deleted is not on the list.

2) implement DeleteItem as specified in (1) using an array based implentation.

3) rewrite the specification for DeleteItem so that all copies of the item to be deleted are removed if they exsist.

4) implement DeleteItem specified in (3) using an array based implementation.

Explanation / Answer

And the following is an incomplete implementation of the singly linked list:

What about the case with a dummy head?

Insertion at the head

Insert a new node at the head of the list is straightforward. The main idea is that we create a new node, set its next link to refer to the current head, and then set head to point to the new node.

Java code:

The above is the case with no dummy head. What about the case with a dummy head?

Insertion at the tail

If we keep a reference to the tail node, then it would be easy to insert an element at the tail of the list. Assume we keep a tail node in the class of SLinkedList, the idea is to create a new node, assign its next reference to point to a null object, set the next reference of the tail to point to this new object, and then assign the tail reference itself to this new node. Initially both head and tail point to null object.

/** Node of a singly linked list of strings. */
public class Node {
private String element; // we assume elements are character strings
private Node next;
/** Creates a node with the given element and next node. */
public Node(String s, Node n) {
    element = s;
    next = n;
}
/** Returns the element of this node. */
public String getElement() { return element; }
/** Returns the next node of this node. */
public Node getNext() { return next; }
// Modifier methods:
/** Sets the element of this node. */
public void setElement(String newElem) { element = newElem; }
/** Sets the next node of this node. */
public void setNext(Node newNext) { next = newNext; }
}

And the following is an incomplete implementation of the singly linked list:

/** Singly linked list .*/
public class SLinkedList {
protected Node head; // head node of the list
protected long size; // number of nodes in the list
/** Default constructor that creates an empty list */
public SLinkedList() {
    head = null;
    size = 0;
}
// ... update and search methods would go here ...
}

What about the case with a dummy head?

/** Singly linked list .*/
public class SLinkedList {
protected Node head; // head node of the list
protected long size; // number of nodes in the list
/** Default constructor that creates an empty list */
public SLinkedList() {
    head = new Node(null, null); // create a dummy head
    size = 0;
}
// ... update and search methods would go here ...
} Insertion in a Singly Linked List

Insertion at the head

Insert a new node at the head of the list is straightforward. The main idea is that we create a new node, set its next link to refer to the current head, and then set head to point to the new node.

Algorithm addFirst(String newData):
create a new node v containing newData
v.setNext(head)
head = v
size = size + 1

Java code:

public void addFirst(String newData)
{
head = new Node(newData, head);
size++;
}

The above is the case with no dummy head. What about the case with a dummy head?

Insertion at the tail

If we keep a reference to the tail node, then it would be easy to insert an element at the tail of the list. Assume we keep a tail node in the class of SLinkedList, the idea is to create a new node, assign its next reference to point to a null object, set the next reference of the tail to point to this new object, and then assign the tail reference itself to this new node. Initially both head and tail point to null object.

Algorithm addLast(String newData):
create a new node v containing newData
  v.setNext(null)
if (head == null) { // list is empty
      head = v
} else { // list is not empty    
      tail.setNext(v)
}
tail = v
size = size + 1

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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