I have created a doubly linked list, that appends new nodes to the doubly linked list. I am currently trying to work on deleting a node at a specific index.
This is my node class, which initializes three variables, next, previous, and it imports objects from a student class that I have. Shouldn't the for loop iterate up to the value of the index entered and then redirect the next value?
Node Class:
public class Node {
Student student;
Node next;
Node previous;
public Node(Student student) {
this.student = student;
this.next = null;
this.previous = null;
}
@Override
public String toString() {
return student.toString();
}
}
DoublyLinkedList Class:
public class DoublyLinkedList <T extends Comparable<T>> {
protected Node head;
protected Node tail;
int size=0;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
public Node append(Student student) {
Node append = new Node(student);
if (head == null) {
head = append;
tail = append;
}
else {
append.previous = tail;
tail.next = append;
tail = tail.next;
}
size ;
return append;
}
public void delete(int location) throws IllegalArgumentException {
Node current = head;
int counter = 1;
int i;
// Exception error for cases in which there are no nodes
if (head == null || location < 0)
throw new IllegalArgumentException("Sorry but the DLL is NULL, please add nodes");
// Cases in which the person wants to delete the head at index 0
if (location == 0) {
/* If the node that is next is not null we make that the head
*/
if (head.next != null) {
head.next.previous = head;
}
}
for (i = 1; head != null && i < location; i ) {
head = head.next;
}
if (head == null)
head = head.next.previous;
}
}
I believe the cases that I made for situations where the head is null, a negative value is entered, and the head node is being deleted are correct. I believe the problem is iterating up the given parameter (index of node being deleted). I did a for loop that iterates up to the given index. What I was trying to do is once the value of head reaches the parameter entered, it would redirect the next of the Node it iterated up to. Is this logic correct and the syntax wrong or is there another logic for a case like this?
CodePudding user response：
Your DoublyLinkedList class is generic. Therefore class Node should also be generic. Consequently, class Student needs to implement interface Comparable.
Since you have a doubly-linked list, method delete also needs to update tail in class DoublyLinkedList.
Since class DoublyLinkedList has member size, method delete also needs to update that member as well.
Because class DoublyLinkedList has member size, the parameter, location, of method delete is valid if it is not negative and also if it is less than size.
There are three, separate cases that method delete needs to handle:
- You are deleting the first
NodeinDoublyLinkedList.- You also need to handle the case where there is only one
NodeinDoublyLinkedList.
- You also need to handle the case where there is only one
- You are deleting the last
NodeinDoublyLinkedList. - You are deleting a
Nodewhich is neither the first nor the last.- You also need to handle the case where you are deleting the second last
Node.
- You also need to handle the case where you are deleting the second last
You didn't post code for class Student so I just made up a class.
In the below code, I added toString method in class DoublyLinkedList simply in order to help "visualize" the list.
I also added a main method to class DoublyLinkedList to demonstrate use of method delete.
public class DoublyLinkedList<T extends Comparable<T>> {
protected Node<T> head;
protected Node<T> tail;
int size = 0;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
public Node<T> append(T student) {
Node<T> append = new Node<>(student);
if (head == null) {
head = append;
tail = append;
}
else {
append.previous = tail;
tail.next = append;
tail = tail.next;
}
size ;
return append;
}
public void delete(int location) throws IllegalArgumentException {
// Exception error for cases in which there are no nodes
if (head == null || location < 0 || location >= size)
throw new IllegalArgumentException("Sorry but the DLL is NULL, please add nodes");
// Cases in which the person wants to delete the head at index 0
if (location == 0) {
head = head.next;
if (head != null) {
head.previous = null;
}
if (size == 2) {
tail = head;
}
}
else if (location == size - 1) {
tail = tail.previous;
tail.next = null;
}
else {
Node<T> current = head;
for (int i = 1; i < location; i ) {
current = current.next;
}
current.next = current.next.next;
if (current.next == null) {
tail = current;
}
else {
current.next.previous = current;
}
}
size--;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("[%d]:", size));
Node<T> current = head;
while (current != null) {
sb.append(current);
sb.append('\u2192');
current = current.next;
}
return sb.toString();
}
public static void main(String[] args) {
DoublyLinkedList<Student> dll = new DoublyLinkedList<>();
System.out.println(dll);
dll.append(new Student());
System.out.println(dll);
dll.append(new Student());
System.out.println(dll);
dll.append(new Student());
System.out.println(dll);
dll.append(new Student());
System.out.println(dll);
dll.delete(1);
System.out.println(dll);
}
}
class Student implements Comparable<Student> {
private static int counter;
private int id;
public Student() {
id = counter;
}
@Override
public int compareTo(Student o) {
return id - o.id;
}
public boolean equals(Object obj) {
boolean equal = this == obj;
if (!equal) {
if (obj instanceof Student) {
Student other = (Student) obj;
equal = id == other.id;
}
}
return equal;
}
public int hashCode() {
return id;
}
public String toString() {
return String.format("%d", id);
}
}
class Node<T> {
T student;
Node<T> next;
Node<T> previous;
public Node(T student) {
this.student = student;
this.next = null;
this.previous = null;
}
@Override
public String toString() {
return student.toString();
}
}
CodePudding user response：
This seems to be homework, so I won't give a full code, but pointers to where mistakes are. If this isn't the case feel free to comment and I'll remove this. This should be a comment, but this is too long to fit in the comment section.
There are four things that seem off in the delete method:
When iterating over the array to find the node to delete, the head is modified.
for (i = 1; head != null && i < location; i ) {
head = head.next;
}
This will permanently modify the head of the doubled linked list, meaning that the nodes before the new head are lost.
You should use a variable to iterate (I believe current was supposed to be that ?)
When you delete the head
It's correct that there is additional work to do when the location to delete is the head, but head.next.previous = head; does nothing : head is already the previous node of head.next.
When you delete the tail
There is additional work to do when you delete the head, but also when you delete the tail.
You never actually remove anything
Other than the lost nodes when iteration, you never remove any node form the list.
I suggest you start with simple case and see what your current implementation does, then try to correct it. You can also do it pen and paper by drawing the double linked list, this could help you build an intuition on what steps should be done.