[FIXED] How to add a new node at the start of a doubly linked list?

Issue

I have created a class SLList where I'm going to take a doubly linked list SLlist and I'm trying to find how to add a new node of any type to the start of that doubly linked list.

In order to do this, I have made some sentinels firstsen and lastsen since I was told that this approach would be a lot better to do.

Now, as said earlier, I'm trying to add a new node to the start of that doubly linked list using a function public void addFirst(T) {}.

Here is my code so far...

public class SLList{
    private class IntNode<T> {
        private int data;
        private IntNode previous;
        private IntNode next;

        public IntNode (int data, IntNode previous, IntNode next) {
            this.data = data;
            this.previous = previous;
            this.next = next;

        }
    }
    IntNode firstsen;
    IntNode Lastsen;
    public SLList(){
        firstsen = new IntNode(0,null,null );
        Lastsen = new IntNode(0, firstsen, null);
        firstsen.next = Lastsen;


    }
    public void addFirst(T) {}


}

However, I'm stumped on what I have to do next because I'm new to object oriented programming, so if anyone would be willing to help, that would be really helpful.

Furthermore, I would also appreciate if anyone could explain how to edit my code to accept any generic type

Thank you, Dave

Solution

Make SLList generic as SLList<T>, and replace any occurrence of int with T.

When using the sentinel pattern in a doubly linked list, realise that you only need one sentinel node, which will serve for marking both the end end the beginning of the list. It starts out as a self-referencing node. For this purpose it would be elegant to provide a constructor without arguments.

In addFirst you obviously create a node instance. In total 4 node references need to get initialised when inserting a new node. Two of those are set by the IntNode constructor (these are references from the new node to its neighbors), and two more references need to be set in already existing nodes (these are references to the new node from its neighbors).

The new node reference thus gets assigned to sentinel.next and to node.next.previous (where node is the new instance).

Here is how that would look:

public class SLList<T>{ // Add Generics here
    private class IntNode {
        private T data;
        private IntNode previous;
        private IntNode next;

        public IntNode (T data, IntNode previous, IntNode next) {
            this.data = data;
            this.previous = previous;
            this.next = next;
        }
        
        public IntNode () { // Self-referencing node
            next = previous = this;
        }
    }
    
    IntNode sentinel; // One sentinel can serve both purposes

    public SLList(){
        sentinel = new IntNode(); // Self referencing previous/next
    }

    public void addFirst(T data) {
        IntNode node = new IntNode(data, sentinel, sentinel.next);
        sentinel.next = node;
        node.next.previous = node;
    }

    public void addLast(T data) {
        IntNode node = new IntNode(data, sentinel.previous, sentinel);
        sentinel.previous = node;
        node.previous.next = node;
    }
}

Answered By - trincot
Answer Checked By - Willingham (JavaFixing Volunteer)