Issue creating my own LinkedList class in Java

Question

Okay, so I'm trying to create my own LinkedList class (with generic typing) in Java but am running into problems. I have created a LinkedListNode class which basically sets and gets the next and right pointers and also the node's key. My LinkedList class code is posted below, if you compile and run you'll see it's not setting the list up as it should. At the moment, I am trying to insert node y after node x, but my printout looks like:

Key: 5 - prev key: 6 - next key: 6 Key: 6 - prev key: null - next key: null

My code:

public class LinkedList<T> {

    private LinkedListNode<T> m_head = null;
    private LinkedListNode<T> m_tail = null;

    public LinkedList() {
        m_head = new LinkedListNode<T>();
        m_tail = new LinkedListNode<T>();
        m_head.setNext(m_tail);
        m_tail.setPrev(m_head);
    }

    public LinkedListNode<T> getHead() {
        return m_head;
    }

    public LinkedListNode<T> getTail() {
        return m_tail;
    }

    public void insert(LinkedListNode<T> node, LinkedListNode<T> prev_node) {
        prev_node.getNext().setPrev(node);
        node.setPrev(prev_node);
        node.setNext(prev_node.getNext());
        prev_node.setNext(node);
    }

    public void delete(LinkedListNode<T> node) {

    }

    @Override
    public String toString() {
        LinkedListNode<T> pointer = m_head.getNext();
        String result = "";
        while(pointer.getKey() != null) {
            T prev_key = pointer.getPrev() == null ? null : pointer.getPrev().getKey();
            T next_key = pointer.getNext() == null ? null : pointer.getNext().getKey();
            result += "\nKey: " + pointer.getKey() + " - prev key: " + prev_key + " - next key: " + next_key;
            pointer = pointer.getNext();
        }
        return result;
    }

    public static void main(String[] args) {
        LinkedListNode<Integer> x = new LinkedListNode<Integer>(5);
        LinkedListNode<Integer> y = new LinkedListNode<Integer>(6);
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.insert(x, list.getHead());
        list.insert(y, x);
        System.out.println(list.toString());
    }

}

LinkedListNode.java:

public class LinkedListNode<T> {

    private T m_key;
    private LinkedListNode<T> m_next = null;
    private LinkedListNode<T> m_prev = null;

    public LinkedListNode() {

    }

    public LinkedListNode(T key) {
        m_key = key;
    }

    public T getKey() {
        return m_key;
    }

    public void setKey(T key) {
        m_key = key;
    }

    public LinkedListNode<T> getNext() {
        return m_next;
    }

    public LinkedListNode<T> getPrev() {
        return m_next;
    }

    public void setNext(LinkedListNode<T> node) {
        m_next = node;
    }

    public void setPrev(LinkedListNode<T> node) {
        m_prev = node;
    }

}

It would be helpful to provide us with the LinkedListNode class as well, so people could actually test any suggested changes before posting an answer, not to mention the possibility of that containing a bug. — Bernhard Barker
– Bernhard Barker, Commented Mar 7, 2014 at 12:13

Damian Leszczyński - Vash · Accepted Answer · 2014-03-07 10:04:24Z

0

What you try to implement is Double Linked List (double as you have next and previous).

And you have a problem in your structure design, maintain the head and tail can be issue prone.

You should try to implement it using single element that refer to other.

LinkedListNode<T> header = new LinkedListNode<T>(); 

header.getNext(); // head
header.getPrevious()//tail

The example of insert

 public void insert(T element) { //We add to the begin

     LinkedListNode<T> newElement = LinkedListNode<T>(element);

     newElement.setNext(header); //previous begin we set to be next
     newElement.setPrevious(header.getPrevious()); //previous end we set to be end. 

     newElement.getPrevious().setNext(newElement); //to previous end we set new begin.
     newElement.getNext().setPrevious(newElement); //to previous begin we set new end. 

 }

edited Mar 7, 2014 at 10:04

answered Mar 7, 2014 at 9:46

Damian Leszczyński - Vash

31k9 gold badges64 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Bernhard Barker Over a year ago

Having one element refer to both the head and the tail would be very confusing.

Keir Simmons Over a year ago

Why are you creating the newElement object? If I later change the value of the key of whatever was passed to insert, your method would not auto-update the LinkedList, would it? Is there any way to achieve what I want with my code, or, does anyone know why mine does not work?

Damian Leszczyński - Vash Over a year ago

The Node is part of list and should not be exposed outside. The list should be usable but closed for change from outside world. In your main you must know how to work with object to store correctly the data. When you want to change the you should not change what is in the ndode you might want to change the interior of that object but not itself. The node should be immutable.

Damian Leszczyński - Vash Over a year ago

@Dukeling, That an opinion. For me having two is more confusing.

Collectives™ on Stack Overflow

Issue creating my own LinkedList class in Java

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related