One common variation is the circular, doubly-linked list. As the name suggests,
ID: 3574602 • Letter: O
Question
One common variation is the circular, doubly-linked list. As the name suggests, the Nodes in such a list are doubly-linked, meaning there is a next reference that points to the next Node in the list and there is also a prev reference that points to the previous Node in the list. This permits the list to be traversed forward and backward. Furthermore, these lists are circular, meaning that when you reach the “last” Node in the list, the next pointer of that Node will refer to the “first” Node in the list; likewise, the prev pointer of the “first” Node will refer to the “last” Node in the list. 2 Above is an example of a circular, doubly-linked list containing 5 Nodes. Each Node has a next and a prev pointer that will refer to the next and previous nodes in the list, respectively. When there is only one node in the list, the next and prev pointers of that node should point to itself. As for the DoublyLinkedList object, the only data it has is the listStart Node, which points to the first node in the list (just like in our original LinkedList implementation). Your implementation should not have any other properties than the ones described above. For this assignment, you will implement a class called DoublyLinkedList to represent a circular, doubly-linked list. You can (and should) use the LinkedList example from class as a template and make the necessary changes to the Node and LinkedList classes to reflect the circular and doubly-linked nature of this variation. Your LinkedList class should implement all of the methods that are defined in the original version we looked at in class except for the travLinkedList() and trav() methods. Write a main program that thoroughly tests your implementation of the class. You will submit your code and your output for this assignment.
this is the node do not change
/**
* Implementation of one Node of a Linked List
*/
//The structure for the node of the linked list
//Separately defined because it is self-referencing
public class Node {
private int data; //the data contained in this Node
private Node next; //pointer to the next Node in the linked list
//While we normally would define constructors, we only want to be able to create new Nodes in the
// context of a LinkedList object. Thus, we will leave only the default constructor defined here,
// leaving the setting of the data to be done when the linked list creates a new node.
//Accessors
public int getData() {
return data;
}
public Node getNext() {
return next;
}
//Mutators
public void setData(int x) {
System.out.println("inside setData");
data = x;
}
public void setNext(Node p) {
next = p;
}
}
this is the linked list that has to be altered
/**
* LinkedList class - defines the structure for a linked list of Node objects and the
* methods used to carry out the basic linked list operations
*/
public class DoubleLinkedList {
private Node listStart; //A linked list is referred just by the first Node of the list
//Default constructor - starts the list as empty
public DoubleLinkedList() {
listStart = null;
}
//Initializing constructor - creates a node to start the list using the value provided
public DoubleLinkedList(int x) {
listStart = new Node(); //create a new Node to be the start
listStart.setData(x); //set the value for the start Node using the passed in parameter
listStart.setNext(null); //set the next pointer to null to signify that is the last Node
}
//newNode() - creates and returns a new node whose data is 0
public Node newNode() {
Node p = new Node();
p.setData(0);
p.setNext(null);
return p;
}
//newNode() - creates and returns a new node whose data is the parameter x
public Node newNode(int x) {
Node p = new Node();
p.setData(x);
p.setNext(null);
return p;
}
//addFront() - creates a new node containing x AND inserts it at the *front* of the list
public void addFront(int x) {
Node p = newNode(x);
p.setNext(listStart); //MUST set the next point of the new node to the old listStart so we don't
// lose the old list
listStart = p; //Once we create the new Node, set the new start of the LinkedList to it
}
//addRear() - creates a new node containing x AND inserts it at the *rear* of the list
public void addRear(int x) {
Node p, q;
//Scan through the list to find the end
//Once this loop is finished, q will point to the last Node in the list
//for (p = listStart, q = null; p != null; q = p, p = p.getNext());
//traverse the list to find the last element.
q = listStart;
while(q.getNext() != null)
q = q.getNext();
//at this point q points to last element in list.
//Invariant -- at this point p MUST be NULL, so we use it to hold a pointer to the new node
p = newNode(x);
//set the next pointer of q (the last Node) to point to our new Node
q.setNext(p);
}
//insertAfter() - Insert value x in a new node to be inserted after Node p
public void insertAfter(int x, Node p) {
Node q = newNode(x); //create a new Node containing x
q.setNext(p.getNext()); //set the next pointer of the new Node to the Node after p
p.setNext(q); //set the next pointer of p to the new Node q
}
//isXThere() - Returns true if there is a Node in the list containing x; returns false otherwise
public boolean isXThere(int x) {
Node p = listStart;
if (p == null) //list is empty, so we know it's not there
return false;
else {
//Scan through the list looking for Node containing x
while (p != null && p.getData() != x)
p = p.getNext();
//Invariant - at this point, either p contains x or we have gone through the entire list
// without finding it
if (p == null)
return false;
else
return true;
}
}
//find() - Return the Node containing x
public Node find(int x) {
Node p;
//Scan through list looking for Node containing x
for (p = listStart; p != null && p.getData() != x; p = p.getNext());
//Invariant -- at this point, either p contains x or is null (we have gone through entire list)
if (p != null)
return p;
else
return null; //Since we searched the entire list without finding it, return null
}
//removeNode() - Removes the Node containins x from the list (if it exists)
public void removeNode(int x) {
Node p, q;
//Scan through the list to see if x is there;
// when loop is done, q will point to the Node before the Node with x
for (p = listStart, q = null; p != null && p.getData() != x; p = p.getNext())
q = p;
//If you find it, remove it
if (p != null) {
if (q == null) //x is at the front so re-adjust pointer to remove the front Node
listStart = p.getNext();
else //splice out the Node with x from list
q.setNext(p.getNext());
}
}
//writeLinkedList() - write the data content of every Node on the list
public void writeLinkedList() {
Node p;
System.out.println("Writing list:");
for (p = listStart; p != null; p = p.getNext())
System.out.println(p.getData());
}
//travLinkedList() - Traverse a list recursively using the function trav()
public void travLinkedList() {
if (listStart != null)
trav(listStart);
System.out.println();
}
//trav() - The auxiliary traversal function that is used recursively
private void trav(Node p) {
if (p != null) {
System.out.print(p.getData() + " ");
trav(p.getNext());
}
}
}
the main class that need work as well
/**
* Driver program to test the linked list functions
*/
public class TestLinkedList {
public static void main(String[] args) {
LinkedList myLinkedList = new LinkedList(); //create a new list
myLinkedList.writeLinkedList(); //should be empty
myLinkedList.addFront(12);
myLinkedList.writeLinkedList(); //should have one Node with data = 12
System.out.println();
myLinkedList.addRear(1);
myLinkedList.writeLinkedList(); //should have a list containing 12 & 1
System.out.println();
myLinkedList.removeNode(12);
myLinkedList.writeLinkedList(); //should have one Node containing 1
}
}
and in java so java programing language please
Explanation / Answer
//The structure for the node of the linked list
//Separately defined because it is self-referencing
//Has to be modified to add previous node
public class Node {
private int data; //the data contained in this Node
private Node next; //pointer to the next Node in the linked list
private Node prev;
//While we normally would define constructors, we only want to be able to create new Nodes in the
// context of a LinkedList object. Thus, we will leave only the default constructor defined here,
// leaving the setting of the data to be done when the linked list creates a new node.
//Accessors
public int getData() {
return data;
}
public Node getNext() {
return next;
}
public Node getPrev() {
return prev;
}
//Mutators
public void setData(int x) {
System.out.println("inside setData");
data = x;
}
public void setNext(Node p) {
next = p;
}
public void setPrev(Node p) {
prev = p;
}
}
//----------------------------------------------
/**
* LinkedList class - defines the structure for a linked list of Node objects and the
* methods used to carry out the basic linked list operations
*/
public class DoubleLinkedList {
private Node listStart; //A linked list is referred just by the first Node of the list
//Default constructor - starts the list as empty
public DoubleLinkedList() {
listStart = null;
}
//Initializing constructor - creates a node to start the list using the value provided
public DoubleLinkedList(int x) {
listStart = new Node(); //create a new Node to be the start
listStart.setData(x); //set the value for the start Node using the passed in parameter
listStart.setNext(listStart); //set the next pointer to itself
listStart.setPrev(listStart); //set prev to itself
}
//newNode() - creates and returns a new node whose data is 0
public Node newNode() {
Node p = new Node();
p.setData(0);
p.setNext(null);
p.setPrev(null);
return p;
}
//newNode() - creates and returns a new node whose data is the parameter x
public Node newNode(int x) {
Node p = new Node();
p.setData(x);
p.setNext(null);
p.setPrev(null);
return p;
}
//addFront() - creates a new node containing x AND inserts it at the *front* of the list
public void addFront(int x) {
Node p = newNode(x);
if(listStart == null)
listStart = p;
p.setNext(listStart); //MUST set the next point of the new node to the old listStart so we don't
p.setPrev(listStart.getPrev());
listStart = p; //Once we create the new Node, set the new start of the LinkedList to it
listStart.getNext().setPrev(listStart);
}
//addRear() - creates a new node containing x AND inserts it at the *rear* of the list
public void addRear(int x) {
Node p, q;
//Scan through the list to find the end
//Once this loop is finished, q will point to the last Node in the list
//for (p = listStart, q = null; p != null; q = p, p = p.getNext());
//traverse the list to find the last element.
q = listStart;
while(q.getNext() != listStart)
q = q.getNext();
//at this point q points to last element in list.
//Invariant -- at this point p MUST be NULL, so we use it to hold a pointer to the new node
p = newNode(x);
p.setPrev(q);
p.setNext(q.getNext());
//set the next pointer of q (the last Node) to point to our new Node
q.setNext(p);
}
//insertAfter() - Insert value x in a new node to be inserted after Node p
public void insertAfter(int x, Node p) {
Node q = newNode(x); //create a new Node containing x
q.setNext(p.getNext()); //set the next pointer of the new Node to the Node after p
p.getNext().setPrev(q);
p.setNext(q); //set the next pointer of p to the new Node q
p.setPrev(p);
}
//isXThere() - Returns true if there is a Node in the list containing x; returns false otherwise
public boolean isXThere(int x) {
Node p = listStart;
boolean flag = true;
if (p == null) //list is empty, so we know it's not there
return false;
else {
//Scan through the list looking for Node containing x
while ( p.getData() != x){
p = p.getNext();
if(p == listStart)
flag = false;
}
//Invariant - at this point, either p contains x or we have gone through the entire list
// without finding it
return flag;
}
}
//find() - Return the Node containing x
public Node find(int x) {
Node p;
//Scan through list looking for Node containing x
for (p = listStart; p != null && p.getData() != x; p = p.getNext());
//Invariant -- at this point, either p contains x or is null (we have gone through entire list)
if (p.getData() == x)
return p;
else
return null; //Since we searched the entire list without finding it, return null
}
//removeNode() - Removes the Node containins x from the list (if it exists)
public void removeNode(int x) {
Node p, q;
//Scan through the list to see if x is there;
// when loop is done, q will point to the Node before the Node with x
for (p = listStart, q = null; p.getData() != x; p = p.getNext()){
q = p;
if(p.getNext() == listStart)
break;
}
//If you find it, remove it
if (p.getPrev().getData() == x) {
if (q == null) //x is at the front so re-adjust pointer to remove the front Node
listStart = p.getNext();
else { //splice out the Node with x from list
q.setNext(p.getNext());
q.getNext().setPrev(q);
}
}
}
//writeLinkedList() - write the data content of every Node on the list
public void writeLinkedList() {
Node p;
System.out.println("Writing list:");
for (p = listStart;p != null; p = p.getNext()){
System.out.println(p.getData());
if(p.getNext() == listStart)
break;
}
}
}
//-----------------------------------------------------
/**
* LinkedList class - defines the structure for a linked list of Node objects and the
* methods used to carry out the basic linked list operations
*/
public class DoubleLinkedList {
private Node listStart; //A linked list is referred just by the first Node of the list
//Default constructor - starts the list as empty
public DoubleLinkedList() {
listStart = null;
}
//Initializing constructor - creates a node to start the list using the value provided
public DoubleLinkedList(int x) {
listStart = new Node(); //create a new Node to be the start
listStart.setData(x); //set the value for the start Node using the passed in parameter
listStart.setNext(listStart); //set the next pointer to itself
listStart.setPrev(listStart); //set prev to itself
}
//newNode() - creates and returns a new node whose data is 0
public Node newNode() {
Node p = new Node();
p.setData(0);
p.setNext(null);
p.setPrev(null);
return p;
}
//newNode() - creates and returns a new node whose data is the parameter x
public Node newNode(int x) {
Node p = new Node();
p.setData(x);
p.setNext(null);
p.setPrev(null);
return p;
}
//addFront() - creates a new node containing x AND inserts it at the *front* of the list
public void addFront(int x) {
Node p = newNode(x);
if(listStart == null)
listStart = p;
p.setNext(listStart); //MUST set the next point of the new node to the old listStart so we don't
p.setPrev(listStart.getPrev());
listStart = p; //Once we create the new Node, set the new start of the LinkedList to it
listStart.getNext().setPrev(listStart);
}
//addRear() - creates a new node containing x AND inserts it at the *rear* of the list
public void addRear(int x) {
Node p, q;
//Scan through the list to find the end
//Once this loop is finished, q will point to the last Node in the list
//for (p = listStart, q = null; p != null; q = p, p = p.getNext());
//traverse the list to find the last element.
q = listStart;
while(q.getNext() != listStart)
q = q.getNext();
//at this point q points to last element in list.
//Invariant -- at this point p MUST be NULL, so we use it to hold a pointer to the new node
p = newNode(x);
p.setPrev(q);
p.setNext(q.getNext());
//set the next pointer of q (the last Node) to point to our new Node
q.setNext(p);
}
//insertAfter() - Insert value x in a new node to be inserted after Node p
public void insertAfter(int x, Node p) {
Node q = newNode(x); //create a new Node containing x
q.setNext(p.getNext()); //set the next pointer of the new Node to the Node after p
p.getNext().setPrev(q);
p.setNext(q); //set the next pointer of p to the new Node q
p.setPrev(p);
}
//isXThere() - Returns true if there is a Node in the list containing x; returns false otherwise
public boolean isXThere(int x) {
Node p = listStart;
boolean flag = true;
if (p == null) //list is empty, so we know it's not there
return false;
else {
//Scan through the list looking for Node containing x
while ( p.getData() != x){
p = p.getNext();
if(p == listStart)
flag = false;
}
//Invariant - at this point, either p contains x or we have gone through the entire list
// without finding it
return flag;
}
}
//find() - Return the Node containing x
public Node find(int x) {
Node p;
//Scan through list looking for Node containing x
for (p = listStart; p != null && p.getData() != x; p = p.getNext());
//Invariant -- at this point, either p contains x or is null (we have gone through entire list)
if (p.getData() == x)
return p;
else
return null; //Since we searched the entire list without finding it, return null
}
//removeNode() - Removes the Node containins x from the list (if it exists)
public void removeNode(int x) {
Node p, q;
//Scan through the list to see if x is there;
// when loop is done, q will point to the Node before the Node with x
for (p = listStart, q = null; p.getData() != x; p = p.getNext()){
q = p;
if(p.getNext() == listStart )
break;
}
//If you find it, remove it
if (p.getData() == x) {
if (q == null) //x is at the front so re-adjust pointer to remove the front Node
listStart = p.getNext();
else { //splice out the Node with x from list
q.setNext(p.getNext());
q.getNext().setPrev(q);
}
}
}
//writeLinkedList() - write the data content of every Node on the list
public void writeLinkedList() {
Node p;
System.out.println("Writing list:");
for (p = listStart;p != null; p = p.getNext()){
System.out.println(p.getData());
if(p.getNext() == listStart)
break;
}
}
}
//---------------------------------------------------------
public class TestLinkedList {
public static void main(String[] args) {
DoubleLinkedList myLinkedList = new DoubleLinkedList(); //create a new list
myLinkedList.writeLinkedList(); //should be empty
myLinkedList.addFront(12);
myLinkedList.writeLinkedList(); //should have one Node with data = 12
System.out.println();
myLinkedList.addRear(1);
myLinkedList.writeLinkedList(); //should have a list containing 12 & 1
System.out.println();
myLinkedList.removeNode(12);
myLinkedList.writeLinkedList(); //should have one Node containing 1
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.