Generic doubly linked list, Data Structure & Algorithms

Assignment Help:

Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList and toArray(Object[] a) must be implemented. You may throw the exception UnsupportedOperationException for subList and toArray(Object[] a). Again, you may not extend any other class when implementing the List interface.

The CS228LinkedList class contains a non-static inner class called Node. Obviously, the instances of Node serve as nodes in the linked list. The Node inner class contains six member variables: data of type T, next of type Node, prev of type Node, id of type int, nc of type int, and pc of type int. You should not declare any other member variables for the Node inner class.

As we learned, the next eld of a node refers to the next node in the list. If the next node does not exist, then next is null. The prev eld refers to the previous node in the list. If the previous node does not exist, then prev is null. The nc (next changes) eld represents the number of times the \next" node has been changed due to deletion or addition. Likewise, the pc (previous changes) eld represents the number of times the \previous" node has been changed due to deletion or addition. Finally, the id eld should hold a non-negative integer that uniquely identi es that particular node.

Along with normal nodes, the CS228LinkedList class needs to include two dummy nodes called head and tail. We consider the list to be empty if it contains only the head and tail nodes. Logically, if the list is empty, then the node next to head is tail, and the node previous to tail is head. Otherwise, the head is previous to the rst normal node, and the rst normal node is next to the head. Likewise, tail is next to the last normal node, and the last normal node is previous to the tail.

The head and tail dummy nodes must have null data elds. Also, the prev eld of head and the next eld of tail must be null. The pc eld of head and the nc eld of tail must be set to 0. When a normal node is rst created and added to the list, its pc and nc elds are set to 0.

Whenever the next eld of a node is modi ed, its nc eld is incremented by 1. Whenever the prev eld of a node is modi ed, its pc eld is incremented by 1. The inner class Node needs to include a toString() method that returns a String representation of the node. The format of a node's string representation is a sequence of values in the following order: the node's id value, the id value of the previous node, the id value of the next node, the toString() form of its data eld, the pc value of the node, and the sc value of the node. For the head, report -1 as the id value of its previous node. For tail, report -1 as the id value of its next node. The toString() form of any null data eld is the string \null". You must also write the private inner class called CS228LinkedListIterator that implements the ListIterator interface. All attributes for this class must be private. You need to implement all methods in the ListIterator interface without throwing any UnsupportedOperationException. Keep in mind that you do not have to include any checks for concurrent modi cation while implementing the CS228LinkedListIterator inner class.

Write a toString() method in the CS228LinkedList class that produces, in iterator order, the toString() representation of each node in the list. The two dummy nodes should also be reported in this list. Finally, you are allowed to use arrays only in the toArray() method.


Related Discussions:- Generic doubly linked list

Fifo, give any example of page replacement using fifo and use your own refe...

give any example of page replacement using fifo and use your own reference string

Algorithms, b) The user will roll two (six-sided) dices and the user will l...

b) The user will roll two (six-sided) dices and the user will lose the game if (s)he gets a value 1 on either any of the two dices & wins otherwise. Display a message to the user w

A linear list of elements in which deletion can be done, A linear list of e...

A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

Programs, Develop a program that accepts the car registration( hint: LEA 43...

Develop a program that accepts the car registration( hint: LEA 43242010)

Structural Induction, Let a be a well-formed formula. Let c be the number o...

Let a be a well-formed formula. Let c be the number of binary logical operators in a. (Recall that ?, ?, ?, and ? are the binary logical operators). Let s be the number of proposit

Compute the shortest paths to all network nodes, (i)  Consider a system usi...

(i)  Consider a system using flooding with hop counter. Suppose that the hop counter is originally set to the "diameter" (number of hops in the longest path without traversing any

Advanced data structures - splay trees, This is a unit of which targeted on...

This is a unit of which targeted on the emerging data structures. Red- Black trees, Splay trees, AA-trees & Treaps are introduced. The learner must explore the possibilities of app

Sorting algorithm is best if the list is already sorted, Which sorting algo...

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

Design a time algorithm, Q. An, array, A comprises of n unique integers fro...

Q. An, array, A comprises of n unique integers from the range x to y(x and y inclusive where n=y-x). Which means, there is only one member that is not in A. Design an O(n) time alg

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd