Need help with method for Circular Doubly Linked List

[Mike Stein]

For the program I have to create, I need to be able to work with the elements of a circular doubly linked list to do the following:

Find an element in the list (specified as an argument)
Insert an element after a specified element (specified as an argument)
Delete an element (specified as an argument)
Display the elements in the list

I can insert elements and display the elements, but I can't figure out how to search for an element, insert an element after a specified element, or delete an element.

What I am having trouble with is passing the elements in the list as arguments for searching, deleting, inserting after an element.

public class doublyLinkedList {
    
    private Node pointer;
    private Node dLL;
    private int count;
    
    /**
     *  Default Constructor
     */
    public doublyLinkedList() {

        count = 0;
    }
    
    private class Node {
        
        Node next;
        Node previous;
        int element;
        
        public Node (int element) {
            
            this.element = element;
        }
        
        public int getElement() {
        
            return this.element;
        }  
    }  

    public void insertElement(int element) {
        
        Node newNode = new Node(element);
        
        if (count == 0) {
            
            dLL = newNode;
            dLL.next = dLL;
            dLL.previous = dLL;
                  
            pointer = dLL;
        } 
        
        else {
            
            newNode.previous = dLL.previous;
            newNode.next = dLL;
            dLL.previous.next = newNode;
            dLL.previous = newNode;
            
            pointer = dLL;
        }
        
        count++;
    }

    public int size() {
        
        int size = 0;
        
        if (pointer == null)
            
            return size;
        
        else {
            
             Node currentNode = pointer;
             
             do {

                 currentNode = currentNode.next;
                 size++;
             
             } while (currentNode != pointer);
        
        }    
        return size;      
    } 

    // This method is wrong because I can't use an index. I have to use the actual element as the argument. 
    public void deleteNode(int index) {
        
        if (index >= count) {
            
            System.out.println("Out of Bounds");
            
                return;
        }
 
        Node currentNode = pointer;
        
        int i = 0;
        
        while (i < index) {
            
            i++;

            currentNode = currentNode.next;
        }
        
        currentNode.previous.next = currentNode.next;
        currentNode.next.previous = currentNode.previous;
        
        count--;
    }
    
    // Not sure how to make this work
    public void remove(int element) {
        
       
    } 
    
    // Cant figure out how to pass the current node and then work with it to insert a new node after
    public void insertAfter(int current, int data) {

    }
   
   // Also stumped with this one
   public void find(int element) {

   }

   // this is working fine
    public void display() {
        
        if (count == 0) {
            
            System.out.println("List is empty.");
            
            return;
        }
        
        Node currentNode = pointer;
        
        System.out.println("The list includes: ");
        
        do {

            System.out.println(currentNode.element);
            
            currentNode = currentNode.next;
        
        } while (currentNode != pointer);
    }  
}

If anyone could give me some insight into how to solve my issues, I would greatly appreciate it.

[Junilu Lacar]

First off, you could choose better names. For example, the name "dLL" does nothing to convey its intent/use at all. It took me a while reading and analyzing the code to figure out that it points to the head Node of the list. A better name would be just that, head. That greatly lightens the conceptual load on whoever reads the code. Be kind to others, choose intention-revealing names.

[Junilu Lacar]

One piece of advice we commonly give around here is to step away from the computer, take pencil and paper and draw and/or write out the procedure in plain English. Pretend you are teaching a ten-year old to do this manually. How would you describe the process in a step by step manner? Once you have that, it's usually an easier process to translate it into code.

Give it a shot with your find method and show us what you come up with.

[Steve Fahlbusch]

Greetings Mike,

First and mostly, please follow what Junilu suggested - it is really important that you understand the data structure before you implement it.

Next, (a really nice hint) if you understand the data structure,then create a null node as your head/tail pointer (i.e.: null data, next points to itself, prev points to itself). If you don’t understand this - don’t worry, just saving you edge case issues.

Understand that all (most) actions in a DLL are done via the current pointer location, so you may want to implement a few methods that manipulate the current pointer - like move next, move prev, move head, move tail, delete (or remove), insert after, note: now an insert prev can be a move prev, insert after.

All that said, there is some issue with the requirements as you said vs the code. Ok the data reference you are using is an int, but the delete seems to be the ‘index’ and not the contents. You need to resolve that.

So to sum up: you can write a few (bunch) of helper methods that you or may not expose to users of your main class that you can use to help you. Like: a print all could be:
moveToHead(), getSize(), while (size>0), getAtPointer(), print(), moveNext(), size— [end while]

Take some time to fully understand double linked lists - then (with pencil and paper) design your code, then and only then start coding.

[Mike Stein]

Okay, so this is what I finally came up with for the linked list. I am still learning so I am well aware that my code isn't as clean or efficient as it should be. If you guys could look it over and possibly give me any suggestions to make it look and work better that would be fantastic. Also, thanks guys for the tips. I found that stepping back and writing down the nodes helped me to visualize what was going on.

public class DoublyLinkedList<T> {
    
    private Node cursor;
   
    private int count;
    
    
    /**
     *  Default Constructor
     */
    public DoublyLinkedList() {

        count = 0;   
    }

    private class Node<T> {
        
        private Node<T> next = null;
        private Node<T> previous = null;
        private final T val;
       
        public Node (T val) {
 
            this.val = val;
        }
        
        public T getValue() {
        
            return this.val;
        }  
        
    }  

    
    public boolean isEmpty() {
        
        return (count == 0);
    }
    
    
    public void add(T val) {
        
 
        Node<T> newNode = new Node<>(val);

        if (isEmpty()) {
            
            cursor = newNode;
            cursor.next = cursor;
            cursor.previous = cursor;

        } 

        else {
            
            newNode.previous = cursor.previous;
            newNode.next = cursor;
            cursor.previous.next = newNode;
            cursor.previous = newNode;

        }
        
        count++;
    }

        public void insertAfterNode(T currentVal, T value) {

        Node<T> newNode = new Node<>(value);

        Node<T> currentNode = cursor;
        
        int i = 0;

        while (i < count) {
            
            if (currentNode.getValue().equals(currentVal)) {
                
                newNode.next = currentNode.next;
        	newNode.previous = currentNode;
        	currentNode.next = newNode;
                
                if (currentNode == cursor)
                        
                    cursor = cursor.previous;
                
                        count++;
        	
                        return;	
            }	
        	currentNode = currentNode.next;
        	i++;
        }

        System.out.println(currentVal + " is not in the list.");
    }
        
    public void removeNode(T val){
        
        if (isEmpty()) {
            
            System.out.println("List is empty.");
        }
        
        else {

            Node<T> nodeToBeRemoved = cursor;
          
            int i = 0;

            while (i < count) {
                
                if (nodeToBeRemoved.getValue().equals(val)) {
                    
                    Node<T> pred = nodeToBeRemoved.previous;
                    Node<T> succ = nodeToBeRemoved.next;
                    
                    pred.next = succ;
                    succ.previous = pred;

                    if (nodeToBeRemoved == cursor)
                        
                        cursor = cursor.next;
                    
                    count--;
                    
                    return;
                }    

                i++;    
                nodeToBeRemoved = nodeToBeRemoved.next;
            } 
            

            System.out.println(val + " is not in the list.");

        }   
    }   

    public void displayValues() {
    	
        Node<T> temp = cursor;
    	
        int i = 0;
        
        System.out.println("List values: ");
        
        while(i < count) {
            
            System.out.println(temp.getValue());
            
            temp = temp.next;
            
            i++;
        }
    }

    public void searchValue(T val) {
     
        Node<T> currentNode = cursor;
        
        int i = 0;
        
        while (i < count) {
            
            if (currentNode.getValue().equals(val)) {
                
                System.out.println(currentNode.getValue() + 
                        " was found");
                return;
            }
            
            currentNode = currentNode.next;
            i++;
        }
        
        System.out.println(val + " is not in the list.");
    }   
}
    

[Junilu Lacar]

One thing I would do is try to eliminate duplicate code. There's some there where you are trying to find a particular node based on the value. Also, I would throw RuntimeExceptions instead of using System.out.println for errors. Client code, like a static main method, can catch the exception and display a user-friendly message.

In pseudo code:

remove node:
   find first node with value X
   if node not found:
      throw ElementNotFoundException

   link foundNode.previous.next = foundNode.next
   link foundNode.next.previous = foundNode.previous

insert after node:
   find first node with value X
   if node not found:
      throw ElementNotFoundException

   create newNode
   newNode.previous = foundNode
   newNode.next = foundNode.next
   newNode.next.previous = newNode
   foundNode.next = newNode

find first node with value X:
   current = head

   while current.value is not X and current.next != head :
       current = current.next

   if current.value is X
       return current
   else
       return null

[Junilu Lacar]

I think you have a bug in this code. What happens when you add some nodes, then remove all the nodes, and then try to add a new node?

[Junilu Lacar]

Look over this code and see if there are things you like better:

package com.coderanch.examples.beginning;

import java.lang.reflect.Array;

public class DoubleLinkedList<E> {

	private Node head;
	private int size = 0;

	private class Node {
		private Node next;
		private Node previous;
		private final Object value;

		private Node(Object value) {
			this.value = value;
			this.next = this;
			this.previous = this;
		}

		private boolean hasValue(Node o) {
			if (this == o) return true;
			if (this.value == null) return o.value == null;
			return this.value.equals(o.value);
		}
	}

	public boolean isEmpty() {
		return (size == 0);
	}
	
	public int size() {
		return size;
	}

	public void add(E val) {
		Node newNode = new Node(val);

		if (head != null) {
			link(newNode, head);
		} else {
			head = newNode;
		}

		size++;
	}

	public void insertAfter(E value, E newValue) {

		Node existing = find(value);
		if (existing == null) 
			throw new IllegalArgumentException("No such element in list");
		
		Node newNode = new Node(newValue);

		link(newNode, existing.next);

		size++;
	}
	
	public void remove(E value) {

		if (isEmpty()) { 
			throw new IllegalStateException("List is empty");
		}
		
		Node node = find(value);
		if (node == null)
			throw new IllegalArgumentException("No such element in list");
		
		if (node == head) {
			head = head.next;
		}
		
		unlink(node);
		
		size--;
		
		if (size == 0) {
			head = null;
		}
	}

	public boolean contains(E value) {
		return find(value) != null;
	}
	
	private void link(Node newNode, Node existing) {
		newNode.next = existing;
		newNode.previous = existing.previous;
		existing.previous.next = newNode;
		existing.previous = newNode;
	}

	private void unlink(Node node) {
		node.next.previous = node.previous;
		node.previous.next = node.next;
		node.next = null;
		node.previous = null;
	}

	private Node find(E value) {
		Node lookingFor = new Node(value);
		Node current = head;
		while (!current.hasValue(lookingFor) && current.next != head)
			current = current.next;
		return current.hasValue(lookingFor) ? current : null;
	}

	public E[] asArray(Class<E> clazz) {
		E[] array = (E[]) Array.newInstance(clazz, size);
		if (!isEmpty()) {
			putAllElementValuesIn(array);
		}
		return array;
	}

	private void putAllElementValuesIn(E[] array) {
		Node current = head;
		array[0] = (E) current.value;
		for (int i = 1; current.next != head; i++) {
			current = current.next;
			array[i] = (E) current.value;
		}
	}
		
}

[Junilu Lacar]

And here are the JUnit tests for it:

package com.coderanch.examples.beginning;

import static org.junit.Assert.*;
import static org.hamcrest.core.Is.*;

import org.junit.Before;
import org.junit.Test;

public class DoubleLinkedListTest {

	private static final int HEAD_VALUE = 1;
	private static final int TAIL_VALUE = 9;
	private static final int VALUE_NOT_IN_LIST = 99999;
	
	private DoubleLinkedList<Integer> testSubject;
	
	@Before
	public void setup() {
		testSubject = new DoubleLinkedList<>();
	}
	
	@Test
	public void size_should_be_zero_when_new_instance() {
		assertThat(new DoubleLinkedList<Object>().size(), is(0));
	}
	
	@Test
	public void isEmpty_should_be_true_when_new_instance() {
		assertTrue(new DoubleLinkedList<Object>().isEmpty());
	}
	
	@Test
	public void add_should_increase_size_by_one() {
		add(1);
		assertThat(size(), is(1));
	}

	@Test
	public void isEmpty_should_be_false_after_add() {
		add(1);
		assertFalse(isEmpty());
	}
	
	@Test
	public void remove_should_decrease_size_by_one() {
		add(1);
		remove(1);
		assertThat(size(), is(0));
	}
	
	@Test
	public void isEmpty_should_be_true_after_remove_when_size_is_1() {
		add(1);
		remove(1);
		assertTrue(isEmpty());
	}

	@Test
	public void asArray_should_return_all_values() throws Exception {
		add(1);
		add(5);
		add(7);
		assertArrayEquals(array(1, 5, 7), asArray());
	}

	@Test
	public void asArray_should_return_zero_length_array_when_empty() throws Exception {
		assertThat(asArray().length, is(0));
	}
	
	@Test
	public void add_puts_new_element_at_the_end() throws Exception {
		add(3);
		add(1);
		add(-7);
		assertThat(asArray()[2], is(-7));
	}

	@Test
	public void remove_all_then_add_an_element_should_give_size_of_1() throws Exception {
		add(3);
		add(1);
		add(8);
		
		remove(3);
		remove(1);
		remove(8);
		
		assertTrue(isEmpty());
		assertArrayEquals(array(), asArray());
		
		add(4);
		assertThat(size(), is(1));
		assertArrayEquals(array(4), asArray());
	}
	
	@Test
	public void removing_head_makes_next_node_the_head() throws Exception {
		add(3);
		add(7);
		add(1);
		
		remove(3);
		
		assertArrayEquals(array(7, 1), asArray());
	}
	
	@Test
	public void list_accepts_null() throws Exception {
		add(null);
		
		assertThat(size(), is(1));
		assertArrayEquals(new Integer[1], asArray());
	}
	
	@Test
	public void can_find_null_element() throws Exception {
		initTestList();
		add(null);
		
		assertTrue(contains(null));
	}
	
	@Test
	public void contains_is_true_when_value_is_in_list() throws Exception {
		initTestList();
		
		assertTrue(contains(HEAD_VALUE));
		assertTrue(contains(TAIL_VALUE));
	}

	@Test
	public void contains_is_false_when_value_is_not_in_list() throws Exception {
		initTestList();
		
		assertFalse(contains(VALUE_NOT_IN_LIST));
	}
	
	private void initTestList() {
		add(HEAD_VALUE);
		add(7);
		add(3);
		add(14);
		add(TAIL_VALUE);
	}
	
	@Test
	public void can_remove_null_value_element() throws Exception {
		add(1);
		add(null);
		assertThat(size(), is(2));
		assertArrayEquals(array(1, null), asArray());
		
		remove(null);
		
		assertThat(size(), is(1));
		assertArrayEquals(array(1), asArray());
	}
	
	private boolean contains(Integer value) {
		return testSubject.contains(value);
	}
	
	private boolean isEmpty() {
		return testSubject.isEmpty();
	}
	
	private int size() {
		return testSubject.size();
	}
	
	private void add(Integer i) {
		testSubject.add(i);
	}
	
	private void remove(Integer i) {
		testSubject.remove(i);
	}
	
	private Integer[] asArray() {
		return testSubject.asArray(Integer.class);
	}
	
	private Integer[] array(Integer... values) {
		return values;
	}
}