Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8329155

Abnormal Behavior in Doubly Linked List Implementation

XMLWordPrintable

      ADDITIONAL SYSTEM INFORMATION :
      OS: windows 11
      JDK version: 11.0.16

      A DESCRIPTION OF THE PROBLEM :
      I am writing to report a potential bug that I have encountered in the JDK 11 version. The issue is related to a doubly linked list implementation, where the removeByData method exhibits abnormal behavior.

      In the provided Java code, when iterating through the linked list to remove an element based on its data, I observed that the prev pointer of the doublyNode becomes self-referential when the loop is about to reach the target element. This behavior is unexpected, as it seems to distort the structure of the linked list.

      Moreover, it is worth noting that this abnormal prev pointer behavior occurs even before the execution of the equals comparison. Specifically, it happens when the loop is just starting, and the condition while (node != null) is being evaluated.

      I have attached the relevant Java file for your reference. I would appreciate it if you could investigate this issue and provide any insights or resolutions. If additional information or clarification is needed, please do not hesitate to reach out.

      PS: The bug occurs in the removeByData() method in /src/main/java/List/DoublyLinkedList/doublyList.java​ on line 46, I hope this helps you to reproduce the bug.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      1. The first step creates a bi-directional chained table node class
      ```java
      public class doublyNode<T> {
          private T data;
          private doublyNode<T> next;
          private doublyNode<T> prev;

          public doublyNode(T data){
              this.data = data;
              this.next = null;
              this.prev = null;
          }
      }
      ```

      2. Then there needs to be a list class that looks like this:
      ```java
      public class doublyList<T> implements NewList<T> {
          private doublyNode<T> head;
          private doublyNode<T> tail;
          private static Integer size = 0;

          public doublyList() {
              head = null;
              tail = null;
          }
      }
      ```

      3. There's a method for this in the list class, and it's this method that's going wrong:
      ```java
          // Delete the first occurrence of the specified value
          public void removeByData(T data) {
              doublyNode<T> node = head;
              while (node != null) {
                  if (node.getData().equals(data)) {
                      if (node.getNext() == null) {
                          head = null;
                          tail = null;
                      } else {
                          node.getNext().setPrev(node.getPrev());
                          node.getPrev().setNext(node.getNext());
                      }
                      size--;
                      break;
                  }
                  node = node.getNext();
              }
          }
      ```

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      list : [60 1 2 10 50 4 5]
      list.removeByData(10);
      output: 60 1 2 50 4 5
      ACTUAL -
      output: 60 1 2 10 50 4 5

      ---------- BEGIN SOURCE ----------
      ```java
      package List.DoublyLinkedList;

      import List.NewList;

      import java.util.Collection;

      public class doublyList<T> implements NewList<T> {
          private doublyNode<T> head;
          private doublyNode<T> tail;
          private static Integer size = 0;

          public doublyList() {
              head = null;
              tail = null;
          }

          // Inserting nodes at the end of a linked table
          public void append(T data) {
              if (head == null) {
                  head = new doublyNode<>(data);
                  tail = head;
              } else {
                  doublyNode<T> node = new doublyNode<>(data);
                  tail.setNext(node);
                  node.setPrev(tail);
                  tail = node;
              }
              size++;
          }

          // Inserting nodes at the head of a linked list
          public void prepend(T data) {
              if (head == null) {
                  head = new doublyNode<>(data);
                  tail = head;
              } else {
                  doublyNode<T> node = new doublyNode<>(data);
                  node.setNext(head);
                  head.setPrev(node);
                  head = node;
              }
              size++;
          }

          // Delete the first occurrence of the specified value
          public void removeByData(T data) {
              doublyNode<T> node = head;
              while (node != null) {
                  if (node.getData().equals(data)) {
                      if (node.getNext() == null) {
                          head = null;
                          tail = null;
                      } else {
                          node.getNext().setPrev(node.getPrev());
                          node.getPrev().setNext(node.getNext());
                      }
                      size--;
                      break;
                  }
                  node = node.getNext();
              }
          }




          // Deletes the node at the specified position
          public void removeByIndex(int index) {
              if (index < 0 || index >= size) {
                  throw new IndexOutOfBoundsException();
              }
              if (index == 0) {
                  head = head.getNext();
                  head.setPrev(null);
              } else if (index == size - 1) {
                  tail = tail.getPrev();
                  tail.setNext(null);
              } else {
                  doublyNode<T> node = head;
                  for (int i = 0; i < index; i++) {
                      node = node.getNext();
                  }
                  node.getPrev().setNext(node.getNext());
                  node.getNext().setPrev(node.getPrev());
              }
              size--;
          }

          // Adds an element after the specified index
          public void insertAfter(T data, int index) {
              if (index < 0 || index >= size) {
                  throw new IndexOutOfBoundsException();
              }
              if (index == 0) {
                  doublyNode<T> node = new doublyNode<>(data);
                  node.setNext(head);
                  head.setPrev(node);
                  head = node;
              } else if (index == size - 1){
                  append(data);
              } else {
                  doublyNode<T> temp = head;
                  for (int i = 0; i < index; i++) {
                      temp = temp.getNext();
                  }
                  doublyNode<T> node = new doublyNode<>(data);
                  node.setNext(temp.getNext());
                  node.setPrev(temp);
                  temp.setNext(node);
              }
              size++;
          }

          @Override
          public void insertBefore(T data, int index) {
              if (index < 0 || index >= size) {
                  throw new IndexOutOfBoundsException();
              }
              if (index == 0) {
                  prepend(data);
              } else if (index == size - 1) {
                  tail.setNext(new doublyNode<>(data));
                  tail.getNext().setPrev(tail);
                  tail = tail.getNext();
              } else {
                  doublyNode<T> temp = head;
                  for (int i = 0; i < index - 1; i++) {
                      temp = temp.getNext();
                  }
                  doublyNode<T> node = new doublyNode<>(data);
                  node.setNext(temp.getNext());
                  node.setPrev(temp);
                  temp.setNext(node);
                  temp.getNext().setPrev(node);
              }
              size++;
          }

          @Override
          public void replace(T data, int index) {
              if (index < 0 || index >= size) {
                  throw new IndexOutOfBoundsException();
              }
              if (index == 0) {
                  head.setData(data);
              } else if (index == size - 1) {
                  tail.setData(data);
              } else {
                  doublyNode<T> temp = head;
                  for (int i = 0; i < index; i++) {
                      temp = temp.getNext();
                  }
                  temp.setData(data);
              }
          }

          @Override
          public void print() {
              doublyNode<T> node = head;
              while (node != null) {
                  System.out.print(node.getData() + " ");
                  node = node.getNext();
              }
              System.out.println();
          }

          public void listOf(T... array) {
              for (T data : array) {
                  append(data);
              }
          }

          public void listOf(Collection<T> collection) {
              for (T data : collection) {
                  append(data);
              }
          }

          public Integer getSize() {
              return size;
          }

      }


      ```java
      package List.DoublyLinkedList;

      public class doublyNode<T> {
          private T data;
          private doublyNode<T> next;
          private doublyNode<T> prev;

          public doublyNode(T data){
              this.data = data;
              this.next = null;
              this.prev = null;
          }

          public T getData() {
              return data;
          }

          public void setData(T data) {
              this.data = data;
          }

          public doublyNode<T> getNext() {
              return next;
          }

          public void setNext(doublyNode<T> next) {
              this.next = next;
          }

          public doublyNode<T> getPrev() {
              return prev;
          }

          public void setPrev(doublyNode<T> prev) {
              this.prev = prev;
          }
      }

      ```

      ```java
      public class Main {
          public static void main(String[] args) {
              doublyList<Integer> list = new doublyList<>();

              list.listOf(1, 2, 3, 4, 5);
              list.print();// 1 2 3 4 5

              list.removeByIndex(2);
              list.print();// 1 2 4 5

              list.insertBefore(10, 2);
              list.print();// 1 2 10 4 5

              list.insertAfter(50, 2);
              list.print();// 1 2 10 50 4 5

              list.prepend(60);
              list.print();// 60 1 2 10 50 4 5

              list.removeByData(10);
              list.print();// 60 1 2 50 4 5
                           // !!! wrong 60 1 2 10 50 4 5


              System.out.println(list.getSize());// 6

              list.replace(99,2);
              list.print();// 60 1 99 50 4 5




          }
      }

      ```
      ```
      ---------- END SOURCE ----------

      FREQUENCY : always


            tongwan Andrew Wang
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated:
              Resolved: