Instructions Part 1 - Implementation of a Doubly Linked List Attached you will find the code for an implementation of a Singly Linked List.
There are 3 files:
Driver.java -- testing the List functions in a main() method.
LinkNode.java -- Class definition for a Node, which is the underlying entity that stores the items for the linked list.
SinglyLinkedList.java -- Class definition for the Singly Linked List. All the heavy lifting happens here.
Task 1 -
Review & Testing: Create a new project and add these classes into the project. Make sure that everything works. You can try out other tests in the main() as needed. Carefully review the code and comments to see that you understand everything that's happening. If anything is unclear, or if there is a bug in my code, then please let me know. A good exercise would be to comment the Driver to list all the operations that are being performed on the list.
Task 2 :
Write a method for the SinglyLinkedList that returns the length of the current list. If the list is empty it should return 0. You can use any implementation whatsoever.
Task 3 - Doubly Linked List Use the SinglyLinkedList code as a guide for implementing a DoublyLinkedList.
You can extend the Node and SinglyLinkedList classes OR you can copy and paste the code into new files and refactor them.
It is your choice. The crucial thing is to see how each of the methods in the Linked List gets modified.
You must implement each of the methods. No doubt, delete() and insert() are the trickiest. Concentrate on having a well defined plan of action before proceeding to code. Visualize clearly what needs to happen for the new implementations.
Layout what changes are needed in notes or a design document which you can use in the report below.
Make sure you have the following additional methods on the DoublyLinkedList:
displayReverse()
addToTail()
Be careful with your implementation and make sure you are maintaining the structural integrity of the LinkedList.
Try one method at a time. Start with the simple ones, viz. add() and addToTail(), make sure each method works correctly before moving to other methods.
Task:4
Report(need in google Doc file): Discuss how you implement each part in detail. Discuss any difficulties faced, and how you resolved those difficulties.
Please see below all three addition instruction which I mention Beginning of the Question .please use in the code
(1) Driver.java package LinkedList;
package LinkedList; public class driver { public static void main(String[] args) { // TODO Auto-generated method stub SinglyLinkedList s = new SinglyLinkedList(); s.display(); s.add(3); s.display(); s.add(5); s.display(); s.add(13); s.display(); s.add(19); s.display(); s.add(23); s.display(); System.out.println(s.search(9)); System.out.println(s.search(3)); System.out.println(s.remove(19)); System.out.println(s.remove(5)); System.out.println(s.remove(23)); s.display(); }
package LinkedList; public class LinkNode { //Data private int item; private LinkNode next; LinkNode(int i){ this.item = i; } //Methods public int getItem() { return item; } public void setItem(int item) { this.item = item; } public LinkNode getNext() { return next; } public void setNext(LinkNode next) { this.next = next; }
ackage LinkedList; public class SinglyLinkedList { //Data private LinkNode head; //Methods //Constructor SinglyLinkedList(){ //Empty Constructor head = null; //Indicate that this is an empty list } /*SinglyLinkedList(int i){ //Second overloaded constructor }*/ //Regular Methods //add() public void add(int item) { //new node with this incoming value; make sure that the next pointer is pointing to the correct place LinkNode newNode = new LinkNode(item); newNode.setNext(head); //This is redundant code, because as a result of the construction, the next reference would have defaulted to null //Once we change null to head then we are generalizing the code without in any way changing the first add //head is pointing to this node head = newNode; } //remove() public boolean remove(int r) { LinkNode remItem = search(r); if(remItem == null) { return false; }else { if(head.getItem() == r) { //special case to deal with head = head.getNext(); return true; } LinkNode iterator = head; //LinkNode previous = head; while(iterator != null) { if(iterator.getNext().getItem() == r) { //LinkNode previous = iterator; break; } iterator = iterator.getNext(); } iterator.setNext(iterator.getNext().getNext()); return true; } } //search() public LinkNode search(int x) { /*if(head == null) { return null; //null indicates item was not found }*/ LinkNode iterator = head; while(iterator != null) { if(iterator.getItem() == x) { return iterator; } iterator = iterator.getNext(); } return null; //null indicates item was not found } //display() public void display() { if(head == null) { System.out.println("Empty List"); return; } //Linked List Traversal LinkNode iterator = head; System.out.print("List: --> "); while(iterator.getNext() != null) { System.out.print(iterator.getItem() + "-->"); iterator = iterator.getNext(); } System.out.println(iterator.getItem() + "--||"); } }
Note:I am using Eclipse so please make sue i can run my code in Eclipse
//########################### PGM START #####################################
package LinkedList;
public class driver {
public static void main(String[] args)
{
// TODO Auto-generated method stub
DoublyLinkedList
s = new DoublyLinkedList();
s.display();
s.add(3);
s.display();
s.add(5);
s.display();
s.add(13);
s.display();
s.add(19);
s.display();
s.add(23);
s.display();
s.displayReverse();
s.addToTail(10);
s.display();
s.displayReverse();
System.out.println("Length of linked list: "+s.listLength());
System.out.println(s.search(9));
System.out.println(s.search(3).getItem());
System.out.println(s.remove(19));
System.out.println(s.remove(5));
System.out.println("Length of linked list: "+s.listLength());
System.out.println(s.remove(23));
s.displayReverse();
s.display();
}
}
//-----------------------------------------------------------------------------------------------------
package LinkedList;
public class LinkNode {
//Data
private int item;
private LinkNode next;
private LinkNode prev;
LinkNode(int i){
this.item = i;
}
//Methods
public int getItem() {
return item;
}
public void setItem(int item) {
this.item = item;
}
public LinkNode getNext() {
return next;
}
public void setNext(LinkNode next) {
this.next = next;
}
public LinkNode getPrev() {
return prev;
}
public void setPrev(LinkNode prev) {
this.prev = prev;
}
}
//--------------------------------------------------------------------------------------------------------------------
package LinkedList;
public class DoublyLinkedList {
//Data
private LinkNode head;
//Methods
//Constructor
DoublyLinkedList(){ //Empty Constructor
head = null; //Indicate that this is an empty
list
}
//Regular Methods
//add()
public void add(int item) {
//new node
with this incoming value; make sure that the next pointer is
pointing to the correct place
LinkNode
newNode = new LinkNode(item);
newNode.setNext(head); //This is redundant code, because as a
result of the construction, the next reference would have defaulted
to null
//Once we change null to head then we are generalizing the code
without in any way changing the first add
newNode.setPrev(null);
if(head!=null)
head.setPrev(newNode);
//head is
pointing to this node
head =
newNode;
}
//function to add item to the end of the
list
public void addToTail(int item) {
LinkNode newNode = new
LinkNode(item);
LinkNode last=head;
newNode.setNext(null);
if (head == null) {
newNode.setPrev(null);
head
= newNode;
return;
}
while (last.getNext() !=
null)
last = last.getNext();
last.setNext(newNode);
newNode.setPrev(last);
}
//remove()
public boolean remove(int r) {
LinkNode remItem = search(r);
if(remItem == null) {
return false;
}else {
if(head.getItem() == r) {
//special case to deal with
head = head.getNext();
head.setPrev(null);
return true;
}
LinkNode iterator = head;
//LinkNode previous = head;
while(iterator != null) {
if(iterator.getNext().getItem() == r) {
//LinkNode previous = iterator;
break;
}
iterator = iterator.getNext();
}
iterator.setNext(iterator.getNext().getNext());
//set the previous pointer if the node deleted is not the last
node
if(iterator.getNext()!=null)
iterator.getNext().setPrev(iterator);
return true;
}
}
//search()
public LinkNode search(int x) {
/*if(head == null) {
return null; //null indicates item was not
found
}*/
LinkNode iterator = head;
while(iterator != null) {
if(iterator.getItem() == x) {
return iterator;
}
iterator = iterator.getNext();
}
return null; //null indicates item was not
found
}
//display()
public void display() {
if(head == null) {
System.out.println("Empty List");
return;
}
//Linked List Traversal
LinkNode iterator = head;
System.out.print("\nTraversal in forward direction \n");
System.out.print("List: --> ");
while(iterator.getNext() != null) {
System.out.print(iterator.getItem() + "-->");
iterator = iterator.getNext();
}
System.out.println(iterator.getItem() + "--||");
}
//function to reverse a list
public void displayReverse() {
//if head is
null print empty list
if(head == null)
{
System.out.println("Empty List");
return;
}
System.out.print("\nTraversal in reverse direction \n");
//iterate
till last node of the list
LinkNode
last = head;
System.out.print("List: --> ");
while(last.getNext() != null) {
last= last.getNext();
}
//from last node print list element till the begining
while
(last.getPrev() != null) {
System.out.print(last.getItem() +
"-->");
last =
last.getPrev();
}
System.out.println(last.getItem() + "--||");
}
//function to find the length of linked
list
public int listLength() {
int count=0;
//if list is not empty
if(head != null) {
LinkNode
temp=head;
//count each
node in the list
while(temp!=null) {
temp=temp.getNext();
count+=1;
}
}
//return count
return count;
}
}
//################################# PGM END
#########################
OUTPUT
#########
Instructions Part 1 - Implementation of a Doubly Linked List Attached you will find the code for ...
Doubly Linked List The assignment is to modify the below code in any way (like changing the method of a function). Time complexity is omitted. Any methods/functions below could be changed into something different. I was thinking of changing the method of getting size of list and maybe change from numbers to letters for nodes. import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { next = null;...
In Java You may add any classes or methods to the following as you see fit in order to complete the given tasks. Modify the LinkedList (or DoubleLinkedList) class and add a method append. append should take another LinkedList (DoubleLinkedList) as input and append that list to the end of this list. The append method should work by doing a few "arrow" adjustments on the boxes and it should not loop through the input list to add elements one at...
Q) Modify the class Linked List below to make it a Doubly Linked List. Name your class DoublyLinkedList. Add a method addEnd to add an integer at the end of the list and a method displayInReverse to print the list backwards. void addEnd(int x): create this method to add x to the end of the list. void displayInReverse(): create this method to display the list elements from the last item to the first one. Create a main() function to test...
BELOW IS THE CODE I ALREADY HAVE Linked List - Delete Modify Lab 5 and include the method to delete a node from the Linked List. In summary: 1) Add the method Delete 2) Method call to delete, with a number that IS in the list 3) Method call to delete, with a number that is NOT in the list - Be sure to include comments - Use meaningful identifier names (constants where appropriate) import java.io.*; 1/ Java program to...
Complete the implementation of the method replace: public class SinglyLinkedList private Node head, public SinglyLinkedListo this(null) public SinglyLinkedList(Node head) [ this.head -head public Node getHeado return head public void setHead(Node head) [ head: this. head Method that creates a Node containing 'item' @param item Value to be added this.headnew Node(item, this.head) * and adds it as the first element in the list *I public void add(int item) Method that finds the node at the given index d replaces its value...
Doubly Linked List Is there a way to further modify/simplify/improve this program? I was thinking of maybe changing how to get size. I'm not sure. import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { next = null; prev = null; data = 0; } /* Constructor */ public Node(int d, Node n, Node p) { data = d; next = n; prev = p; } /* Function...
Part I: Create a doubly linked circular list class named LinkedItemList that implements the following interface: /** * An ordered list of items. */ public interface ItemList<E> { /** * Append an item to the end of the list * * @param item – item to be appended */ public void append(E item); /** * Insert an item at a specified index position * * @param item – item to be...
Data Structures - Singly Linked Lists You will add a method swapNodes to SinglyLinkedList class (below). This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. You may need to traverse the list. package linkedlists; public class SinglyLinkedList<E> implements Cloneable { // ---------------- nested Node class...
Problem 1 Given a linked list of integers, write a function getUnique that removes all duplicates elements in the linked list and returns the new linked list of unique elements (The order does not matter). Example: Input: 1-»2->3->1-2 Output: 1->2->3 public class Node f int iterm Node next; Node(int d) t item = d; next-null; ) import java.util.ArrayList; public class ExtraLab public static void main (String[] args)t PROBLEM 1 System.out.println("PROBLEM 1"); Node head new Node(1); head.next-new Node (2); head.next.next-new Node(3);...