Hi everyone, can somone help me with this Programming Assignment from Data Structures. Thank you. In this assignment, you will use a modified Node structure to create a “Double Ended Doubly Linked List” data structure with extended functionality. 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 Double Ended Doubly Linked List (DEDLL) class definition is as follows:   public class DEDLL {             public int currentSize;             public Node head;             public Node tail; }   This design is a modification of the standard linked list. In the standard that we discussed in class, there is only a head node that represents the first node in the list and each node only contains a reference to the next node in the list until the chain of nodes reach null. In this DEDLL, each node also has a reference to the previous node. The DEDLL also contains a reference to the tail of the list that represents the last node in the list.   For example, a DEDLL with 4 elements may have nodes with values 5, 2, 6, and 8 from head to tail. This means the head node points to 5 and the tail node points to 8. For node 5, its next pointer points to 2 and its previous pointer points to null. For node 2, its next is 6, and its previous is 5. Similarly for node 6, its next is 8 and its previous is 2. Finally, for node 8, its next points to null while its previous points to 6.   Other observations with this structure:   When the DEDLL is empty, both head and tail point to null When the DEDLL has only 1 node, the head and tail point to the same node Part 1 and 2 are in attachments due to 5000 words limitation.

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

Hi everyone, can somone help me with this Programming Assignment from Data Structures. Thank you.

In this assignment, you will use a modified Node structure to create a “Double Ended Doubly Linked List” data structure with extended functionality. 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 Double Ended Doubly Linked List (DEDLL) class definition is as follows:

 

public class DEDLL

{

            public int currentSize;

            public Node head;

            public Node tail;

}

 

This design is a modification of the standard linked list. In the standard that we discussed in class, there is only a head node that represents the first node in the list and each node only contains a reference to the next node in the list until the chain of nodes reach null. In this DEDLL, each node also has a reference to the previous node. The DEDLL also contains a reference to the tail of the list that represents the last node in the list.

 

For example, a DEDLL with 4 elements may have nodes with values 5, 2, 6, and 8 from head to tail. This means the head node points to 5 and the tail node points to 8. For node 5, its next pointer points to 2 and its previous pointer points to null. For node 2, its next is 6, and its previous is 5. Similarly for node 6, its next is 8 and its previous is 2. Finally, for node 8, its next points to null while its previous points to 6.

 

Other observations with this structure:

 

  1. When the DEDLL is empty, both head and tail point to null
  2. When the DEDLL has only 1 node, the head and tail point to the same node

    Part 1 and 2 are in attachments due to 5000 words limitation.
Part 2) Write a main test program that adequately tests all these functions. The test program
can be hard coded or it can be interactive to allow the user to perform any of these functions at
any time. When developing and testing this project, make function calls that cover as many
situations as you can see and manage. This means calling all of your functions at various times
repeatedly to ensure they in different situations. Remember also that there are different
scenarios to test such as:
1. Insert, delete, etc., on empty lists
2. Insert, delete, etc., on lists with only 1 Node
3. Insert, delete, etc., on lists with more than 1 Node
There are a lot of tests to perform. Your grade will be based not only on developing accurate
function code, but also how detailed your test cases are to ensure you've done them properly.
Program notes:
1. You are welcome to use any programming language as long as the node and DEDLL
structure is the same and you create all functions required
2. For search, update, and delete when there are duplicate data values, the code should
act on the first value encountered. For example, if your DEDLL from head to tail was 7-
5-6-5-6-3- 4 – 2, where head is 7 and tail is 2, "searchForward(6)" would return
the 3rd node while "searchReverse(6) would return the 5th node.
Transcribed Image Text:Part 2) Write a main test program that adequately tests all these functions. The test program can be hard coded or it can be interactive to allow the user to perform any of these functions at any time. When developing and testing this project, make function calls that cover as many situations as you can see and manage. This means calling all of your functions at various times repeatedly to ensure they in different situations. Remember also that there are different scenarios to test such as: 1. Insert, delete, etc., on empty lists 2. Insert, delete, etc., on lists with only 1 Node 3. Insert, delete, etc., on lists with more than 1 Node There are a lot of tests to perform. Your grade will be based not only on developing accurate function code, but also how detailed your test cases are to ensure you've done them properly. Program notes: 1. You are welcome to use any programming language as long as the node and DEDLL structure is the same and you create all functions required 2. For search, update, and delete when there are duplicate data values, the code should act on the first value encountered. For example, if your DEDLL from head to tail was 7- 5-6-5-6-3- 4 – 2, where head is 7 and tail is 2, "searchForward(6)" would return the 3rd node while "searchReverse(6) would return the 5th node.
Part 1) The challenge with this exercise is that with each of these functions, you must make
sure each node's next and previous pointers are correctly maintained and the head and tail
pointers are referring to the correct ends of the list. Here are the functions to complete for the
DEDLL:
/* Basic functions */
public DEDLL()
public void addFront(int n)
public void addEnd(int n)
public Node searchForward(int n)
public Node searchReverse(int n)
public boolean updateForward(int o, int n)
public boolean updateReverse(int o, int n)
public boolean deleteForward(int n)
public boolean deleteReverse(int n)
public void printSize()
public void printForward()
public void printReverse()
/* Extended functions */
public void removeDuplicates()
public void deleteAll()
Function descriptions
DEDLL():
This function is the default constructor for the DEDLL and creates an empty list of size 0
and head and tail are null
addFront(int n):
This creates a new node and inserts it in front of the head node. This new node also
becomes the new head of the list. If the list is empty, the head and tail of the list is the
new node
addEnd(int n):
This creates a new node and inserts it after the tail node. This new node also becomes
the new tail of the list. If the list is empty, the head and tail of the list is the new node
searchForward(int n):
This searches the DEDLL for a Node whose data property matches the given n starting
from the head node and traversing each node's next pointer. If a match is found, the
Node is returned. If a match is not found, the function returns null
searchReverse(int n):
This searches the DEDLL for a Node whose data property matches the given n starting
from the tail node and traversing each node's previous pointer. If a match is found, the
Node is returned. If a match is not found, the function returns null
updateForward(int o, int n):
This searches the DEDLL for a Node whose data property matches the given o starting
from the head node and traversing each node's next pointer. If a match is found, the
Node's data element is updated to the given n and the function returns true. If a match is
not found, the function returns false
updateReverse(int o, int n):
This searches the DEDLL for a Node whose data property matches the given o starting
from the tail node and traversing each node's previous pointer. If a match is found, the
Node's data element is updated to the given n and the function returns true. If a match is
not found, the function returns false
deleteForward(int n):
This searches the DEDLL for a Node whose data property matches the given n starting
from the head node and traversing each node's next pointer. If a match is found, the
Node is removed from the DEDLL while keeping the structure intact and the function
returns true. If a match is not found, the function returns false. Remember if the DEDLL
becomes empty or contains only 1 node after a successful delete, the head and tail
pointers must be updated correctly
deleteReverse(int n):
This searches the DEDLL for a Node whose data property matches the given n starting
from the tail node and traversing each node's previous pointer. If a match is found, the
Node is removed from the DEDLL while keeping the structure intact and the function
returns true. If a match is not found, the function returns false. Remember if the DEDLL
becomes empty or contains only 1 node after a successful delete, the head and tail
pointers must be updated correctly
Basic print functions:
Size: displays the number of elements in the DEDLL
Forward: displays all Node data values starting from head and traversing each element
in "next" order to tail. If the list is empty, it prints "Empty List"
Reverse: displays all Node data values starting from tail and traversing each element in
"previous" order to head. If the list is empty, it prints "Empty List"
Extended functions:
removeDuplicates()
Go through the DEDLL and remove nodes that have duplicate values as other nodes.
For example, if the list contains node values of 4 – 5-6-5- 4 – 1-6-6-3- 4,
removeDuplicates will change the list to 4 – 5-6 – 1-3
public void deleteAll()
Delete all nodes in the DEDLL. Remember that the head and tail nodes must be null
after this function completes
Transcribed Image Text:Part 1) The challenge with this exercise is that with each of these functions, you must make sure each node's next and previous pointers are correctly maintained and the head and tail pointers are referring to the correct ends of the list. Here are the functions to complete for the DEDLL: /* Basic functions */ public DEDLL() public void addFront(int n) public void addEnd(int n) public Node searchForward(int n) public Node searchReverse(int n) public boolean updateForward(int o, int n) public boolean updateReverse(int o, int n) public boolean deleteForward(int n) public boolean deleteReverse(int n) public void printSize() public void printForward() public void printReverse() /* Extended functions */ public void removeDuplicates() public void deleteAll() Function descriptions DEDLL(): This function is the default constructor for the DEDLL and creates an empty list of size 0 and head and tail are null addFront(int n): This creates a new node and inserts it in front of the head node. This new node also becomes the new head of the list. If the list is empty, the head and tail of the list is the new node addEnd(int n): This creates a new node and inserts it after the tail node. This new node also becomes the new tail of the list. If the list is empty, the head and tail of the list is the new node searchForward(int n): This searches the DEDLL for a Node whose data property matches the given n starting from the head node and traversing each node's next pointer. If a match is found, the Node is returned. If a match is not found, the function returns null searchReverse(int n): This searches the DEDLL for a Node whose data property matches the given n starting from the tail node and traversing each node's previous pointer. If a match is found, the Node is returned. If a match is not found, the function returns null updateForward(int o, int n): This searches the DEDLL for a Node whose data property matches the given o starting from the head node and traversing each node's next pointer. If a match is found, the Node's data element is updated to the given n and the function returns true. If a match is not found, the function returns false updateReverse(int o, int n): This searches the DEDLL for a Node whose data property matches the given o starting from the tail node and traversing each node's previous pointer. If a match is found, the Node's data element is updated to the given n and the function returns true. If a match is not found, the function returns false deleteForward(int n): This searches the DEDLL for a Node whose data property matches the given n starting from the head node and traversing each node's next pointer. If a match is found, the Node is removed from the DEDLL while keeping the structure intact and the function returns true. If a match is not found, the function returns false. Remember if the DEDLL becomes empty or contains only 1 node after a successful delete, the head and tail pointers must be updated correctly deleteReverse(int n): This searches the DEDLL for a Node whose data property matches the given n starting from the tail node and traversing each node's previous pointer. If a match is found, the Node is removed from the DEDLL while keeping the structure intact and the function returns true. If a match is not found, the function returns false. Remember if the DEDLL becomes empty or contains only 1 node after a successful delete, the head and tail pointers must be updated correctly Basic print functions: Size: displays the number of elements in the DEDLL Forward: displays all Node data values starting from head and traversing each element in "next" order to tail. If the list is empty, it prints "Empty List" Reverse: displays all Node data values starting from tail and traversing each element in "previous" order to head. If the list is empty, it prints "Empty List" Extended functions: removeDuplicates() Go through the DEDLL and remove nodes that have duplicate values as other nodes. For example, if the list contains node values of 4 – 5-6-5- 4 – 1-6-6-3- 4, removeDuplicates will change the list to 4 – 5-6 – 1-3 public void deleteAll() Delete all nodes in the DEDLL. Remember that the head and tail nodes must be null after this function completes
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Operations of Linked List
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education