Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

I'm having a hard time understanding how to create these functions. Any help to get me started on this would be highly appreciated. If you

I'm having a hard time understanding how to create these functions. Any help to get me started on this would be highly appreciated. If you can please explain what you're doing that would be extremely helpful. I'm using Java to create this Circular Doubly Linked List data structure. At the bottom is the full source code that was provided to me for a "standard" Linked List. From my understanding I should be able to modify that to create the functions I need for the CDLL.

The assignment starts here:

In this assignment, 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 CircularDoublyLinkedList

{

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 nodes 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 Nodes previous pointer should also be pointing to the last Node and no previous pointers of every Node are ever pointing to null.

Key observations with this structure:

1. The current node in the CDLL is always pointing to an existing node. If current is null, the CDLL should be empty

2. All Nodes next and previous pointers are pointing to an existing node

3. 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 nodes 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 nodes 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 Nodes 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 Nodes 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

PROVIDED CODE FOR STANDARD LINKED LIST:

public class LinkedList { public Node head; public LinkedList() { head = null; } public void insert(int value) { Node newNode = new Node(); newNode.data = value; newNode.next = head; head = newNode; } public void append(int value) { Node newNode = new Node(); newNode.data = value; newNode.next = null;

if (head == null) head = newNode; else { Node temp = head; while (temp.next != null) temp = temp.next; temp.next = newNode; } } public Node search(int value) { Node temp = head;

while (temp != null) { if (temp.data == value) return temp; temp = temp.next; }

return null; }

public boolean update(int oldValue, int newValue) { Node temp = search(oldValue);

if (temp == null) return false;

temp.data = newValue; return true; } public boolean delete(int value) { Node current = head;

// Situation #1 if (current == null) return false;

// Situation #2 if (current.data == value) { head = current.next; current = null; return true; } // Final situations current = head.next; Node previous = head; while (current != null) { if (current.data == value) { previous.next = current.next; current = null; return true; } current = current.next; previous = previous.next; }

return false; }

public String toString() { String output = ""; Node temp = head; while(temp != null) { output += String.format("%s", temp); temp = temp.next; } output += String.format("null "); return output; } }

public class Node { public int data; public Node next; public Node() { data = -1; next = null; } public String toString() { return String.format("%d ", data); } }

public class LinkedListSupplement {

public static void main(String[] args) { Node oneElement = new Node(); oneElement.data = 25; oneElement.next = null; Node anotherElement = new Node(); anotherElement.data = 35; anotherElement.next = oneElement; System.out.println(anotherElement); System.out.println(oneElement); LinkedList l = new LinkedList(); l.insert(25); l.insert(5); l.insert(15); l.insert(35); l.append(90); System.out.println(l); System.out.println(l.search(15)); System.out.println(l.search(20)); System.out.println(l.update(15,20)); System.out.println(l); System.out.println(l.update(18,28)); System.out.println(l);

System.out.println(l.delete(15)); System.out.println(l); System.out.println(l.delete(35)); System.out.println(l); System.out.println(l.delete(5)); System.out.println(l); } }

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Design Using Entity Relationship Diagrams

Authors: Sikha Saha Bagui, Richard Walsh Earp

3rd Edition

103201718X, 978-1032017181

More Books

Students also viewed these Databases questions

Question

7-16 Compare Web 2.0 and Web 3.0.

Answered: 1 week ago