you will use a modified Node structure to create a “Circular Doubly Linked List”
ID: 3705974 • Letter: Y
Question
you will use a modified Node structure to create a “Circular Doubly Linked List” data structure. The Node structure is defined as follows (we will use integers for data elements):
public class Node
{
public int data;
public Node next;
public Node previous;
}
The Circular Linked List class definition is as follows:
public class CircularLinkedList
{
public int currentSize;
public Node current;
}
This design modifies the standard linked list. In the standard that we discussed in class, there is a head node that represents the first node in the list and each node contains a reference to the next node in the list until the chain of nodes reach null. In this Circular Doubly Linked List (CDLL), each node has a reference to a next and previous node. When new Node elements are added to the CDLL, the structure looks like a standard linked list with the last node’s next pointer pointing to the first. In this way, no “next” pointers of every Node in the CDLL are ever pointing to null.
Since this is also a doubly linked list, the “previous” pointers of each Node are pointing to the Node behind it in the CDLL. Also, since this is a CDLL, the first Node’s previous pointer should also be pointing to the last Node and no “previous” pointers of every Node are ever pointing to null.
For example, if a CDLL has elements “5”, “3” and “4” and “current” is pointing to “3”, the CDLL should look like:
Key observations with this structure:
The current node in the CDLL is always pointing to an existing node. If current is null, the CDLL should be empty
All Nodes’ next and previous pointers are pointing to an existing node
Traversing all elements means starting at the current node and going in either direction until you come back to the current node
Part 1) Complete the following functions for the CDLL:
public CircularDoublyLinkedList()
public void insertBeforeCurrent(int n)
public void insertAfterCurrent(int n)
public Node search(int n)
public boolean update(int o, int n)
public boolean delete(int n)
public void printSize()
public void printCurrent()
public void printForward()
public void printReverse()
The requirements for each function are as follows:
CircularDoublyLinkedList():
This function is the default constructor for the CDLL and creates an empty list of size 0
insertBeforeCurrent(int n):
This creates a new node and inserts it “behind” the current node. If the list is empty, the new node’s next and previous pointers point to itself. If the list has at least 1 element, the new node is placed “behind” current while keeping the CDLL structure intact. When complete, the new node inserted is the new “current” node
insertAfterCurrent(int n):
This creates a new node and inserts it “after” the current node. If the list is empty, the new node’s next and previous pointers point to itself. If the list has at least 1 element, the new node is placed “after” current while keeping the CDLL structure intact. When complete, the new node inserted is the new “current” node
search(int n):
This searches the CDLL for a Node where its data property matches the given n. If a match is found, the Node is returned and the “current” Node in the CDLL is now this Node. If a match is not found, the function returns null and the “current” Node should be the same as when the function started
update(int o, int n):
This searches the CDLL for a Node where its data property matches the given o. If a match is found, the Node’s data element is updated to the given n and the function returns true. The “current” Node in the CDLL is now this Node. If a match is not found, the function returns false and the “current” Node should be the same as when the function started
delete(int n):
This searches the CDLL for a Node where its data property matches the given n. If a match is found, the Node’s is removed from the CDLL while keeping the structure intact and the “current” Node is the Node that is “after” the Node that was removed. The function returns true. If a match is not found, the function returns false and the “current” Node should be the same as when the function started
print functions:
Size: displays the number of elements in the CDLL
Current: displays the data value of the current element in the CDLL. If the list is empty, it prints “Empty List”
Forward: displays all Node data values starting from current and traversing each element in “next” order. The “current” Node should be the same when the function completes. If the list is empty, it prints “Empty List”
Reverse: displays all Node data values starting from current and traversing each element in “previous” order. The “current” Node should be the same when the function completes. If the list is empty, it prints “Empty List”
Part 2) Write a main test program that allows the user to interactively test all these functions. The user must be able to insert, change, delete and search elements at any time and display the CDLL using any of the four print functions required. The demo of the program will be such that I will be testing to make sure everything works to my satisfaction.
When developing and testing this project, remember every function (except the constructor) should be dealing with 3 scenarios:
Empty lists
Lists with only 1 Node
Lists with more than 1 Node
Part 3) Analysis: At the conclusion of the demo, hand in a printout of an analysis of these functions:
What is the Big-O performance category in the worst case of the insert*, search, update and delete functions using compare operations
How does this function compare to the singly standard linked list version (compare Big-Os for insert, update, search and delete)
Summarize what you think are:
Advantages to using this data structure
Disadvantages to using this data structure
Would a stack, queue or priority queue benefit from using this structure, why or why not for each?
Based on all this, is the increased amount of code worth doing over single standard linked lists? (If your answer is “it depends”, then what does it depend on?)
Program notes:
The code samples above are in Java. You are welcome to use any other programming language as long as the node and circular doubly linked list structure is the same and you create all functions required
Assume memory is available and data entry from the user is correct. The focus is on the data structure and not on user entry data handling
The program should support duplicate data values and the code should not need to be any different because of it. I may or may not test for duplicate values
Group work: I recommend working on your own, but you are welcome to work in pairs. If you work in pairs, put both names on the work you submit. Working in groups of 3 or more is not allowed. I also recommend that both team members understand the details of all code developed.
As such, please avoid submitting work that is exactly the same or eerily similar across individuals and teams. If 2 individuals are sharing code, work together as a team instead. I also encourage collaboration so please do share ideas and such across individuals and teams. I understand function code will be similar across students, but when I look at the code during the demo, know that I've done enough teaching to spot the difference between work ideas that are shared between students and work that is copied.
Ask questions and draw pictures. Get a head start and submit work soon. I recommend completing as much of the assignment as you can, if not all, by Spring break as the 2nd programming project will likely be assigned around that time.
CDLL Example current0x4245ABCO 3 0x44001FAC 0x28ABDD92 4 0x28ABDD92 0x4245ABCO 0x4245ABCO 0x44001FACExplanation / Answer
package circularlinkedlist;
public class CircularDoublyLinkedList {
public int currentSize;
public Node current;
public CircularDoublyLinkedList() {
currentSize = 0;
}
public void insertBeforeCurrent(int n) {
Node node = new Node();
node.data = n;
if (currentSize == 0) {
node.next = node.previous = node;
current = node;
} else {
current.previous.next = node;
node.next = current;
current.previous = node;
node.previous = current.previous;
}
current = node;
currentSize++;
}
public void insertAfterCurrent(int n) {
Node node = new Node();
node.data = n;
if (currentSize == 0) {
node.next = node.previous = node;
} else {
node.next = current.next;
node.previous = current;
current.next = node;
}
current = node;
currentSize++;
}
public Node search(int n) {
if (current == null) {
return null;
}
Node temp = current;
do {
if (temp.data == n) {
current = temp;
return temp;
}
temp = temp.next;
} while (temp != current);
return null;
}
public boolean update(int o, int n) {
if (current.data == o) {
current.data = n;
return true;
}
Node next;
do {
next = current.next;
if (next.data == o) {
next.data = n;
current = next;
return true;
}
} while (next != current);
return false;
}
public boolean delete(int n) {
if (current == null) {
return false;
}
Node temp = current;
do {
if (temp.data == n) {
temp.next = temp.next.next;
current = temp.next;
temp.next.previous = temp.previous;
currentSize--;
return true;
}
} while (temp != current);
return true;
}
public void printSize() {
System.out.println("Size: " + currentSize);
}
public void printCurrent() {
if (current == null) {
System.out.println("Empty List");
return;
}
System.out.println(current.data);
}
public void printForward() {
if (current == null) {
System.out.println("Empty List");
return;
}
Node temp = current;
while (temp.next != current) {
System.out.println(temp.data);
temp = temp.next;
}
current = current.previous;
}
public void printReverse() {
if (current == null) {
return;
}
Node temp = current;
do {
System.out.println(temp.data);
temp = temp.previous;
} while (temp != current);
current = current.next;
}
public static void main(String[] args) {
CircularDoublyLinkedList CDLL = new CircularDoublyLinkedList();
CDLL.insertAfterCurrent(5);
CDLL.insertAfterCurrent(51);
CDLL.insertAfterCurrent(15);
CDLL.printCurrent();
CDLL.insertBeforeCurrent(39);
CDLL.printCurrent();
CDLL.printSize();
System.out.println(CDLL.delete(39));
CDLL.printSize();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.