Over the next 2 weeks we’ll be writing a doubly linked list whose nodes hold an
ID: 3681725 • Letter: O
Question
Over the next 2 weeks we’ll be writing a doubly linked list whose nodes hold an integer. They can hold anything else you want to use. The requirements are split into week 1 and week 2. You are free to work ahead and submit more than the minimal requirement for week 1. Remember: it is better to submit a program that works and is missing a few features than to try to implement all the features at once and having a program that doesn’t work.
week 1 Create a node class that has the necessary fields for a singly linked list and a data field that holds a number.
Create methods to insert, remove, and edit nodes
Create a method to traverse the list and print all the data.
Create a main method that instantiates a list and demonstrates that it works
. week 2 Edit your node class from last week to have the fields required for a doubly linked list
. Edit your methods so that you can still insert and remove nodes
Add a method to traverse the list backwards.
In your main method, demonstrate that all of your original singly-linked-list methods still work and demonstrate that your new doubly-linked-list methods work.
Explanation / Answer
I am implementing this above problem in java code since it not mentioned which program to use
package com.java2novice.ds.linkedlist;
import java.util.NoSuchElementException;
public class DoublyLinkedListImpl<E> {
private Node head;
private Node tail;
private int size;
public DoublyLinkedListImpl() {
size = 0;
}
/**
* this class keeps track of each element information
* @author java2novice
*
*/
private class Node {
E element;
Node next;
Node prev;
public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
/**
* returns the size of the linked list
* @return
*/
public int size() { return size; }
/**
* return whether the list is empty or not
* @return
*/
public boolean isEmpty() { return size == 0; }
/**
* adds element at the starting of the linked list
* @param element
*/
public void addFirst(E element) {
Node tmp = new Node(element, head, null);
if(head != null ) {head.prev = tmp;}
head = tmp;
if(tail == null) { tail = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* adds element at the end of the linked list
* @param element
*/
public void addLast(E element) {
Node tmp = new Node(element, null, tail);
if(tail != null) {tail.next = tmp;}
tail = tmp;
if(head == null) { head = tmp;}
size++;
System.out.println("adding: "+element);
}
/**
* this method walks forward through the linked list
*/
public void iterateForward(){
System.out.println("iterating forward..");
Node tmp = head;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.next;
}
}
/**
* this method walks backward through the linked list
*/
public void iterateBackward(){
System.out.println("iterating backword..");
Node tmp = tail;
while(tmp != null){
System.out.println(tmp.element);
tmp = tmp.prev;
}
}
/**
* this method removes element from the start of the linked list
* @return
*/
public E removeFirst() {
if (size == 0) throw new NoSuchElementException();
Node tmp = head;
head = head.next;
head.prev = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
/**
* this method removes element from the end of the linked list
* @return
*/
public E removeLast() {
if (size == 0) throw new NoSuchElementException();
Node tmp = tail;
tail = tail.prev;
tail.next = null;
size--;
System.out.println("deleted: "+tmp.element);
return tmp.element;
}
public static void main(String a[]){
DoublyLinkedListImpl<Integer> dll = new DoublyLinkedListImpl<Integer>();
dll.addFirst(10);
dll.addFirst(34);
dll.addLast(56);
dll.addLast(364);
dll.iterateForward();
dll.removeFirst();
dll.removeLast();
dll.iterateBackward();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.