I'm trying to visualize a Linked List, I want to insert a Node at the head and push the other node to next

Question

What I'm trying to do is insert a node after the head. Insert at any position, and when I insert at head: I want the previous head to move to head.next.

class Node{

Node next;
Node previous;
int data;

public Node(int data){
    this.data = data;
}

}
public class LinkedList {
Node head;
public Node push(int data){
Node newNode = new Node(data);
if(head == null){
newNode.next = head;
head = newNode;
}
else{
newNode.next = head.next;
head.next = new Node(data);            
}        
return head;
}

public Node insertAtEnd(int data){
    Node temp = this.head;
    while(temp!=null){
    temp = temp.next;
}
    return temp = new Node(data);
}

Main

LinkedList ll = new LinkedList();

         ll.push(15);
         ll.push(4);
         ll.push(78);
         ll.push(55);

         ll.insertAtEnd(80);
         ll.printList();

         int s = ll.getSize();
         System.out.println(s);

Code is only outputting certain Nodes and not all nodes in a list.

See [Doubly linked list - Inserting a node](https://en.wikipedia.org/wiki/Doubly_linked_list#Inserting_a_node) on Wikipedia. — Andreas, Jul 22 '19 at 04:34
public static void main(String[] args) { LinkedList ll = new LinkedList(); ll.push(15); ll.push(4); ll.push(78); ll.push(55); ll.insertAtEnd(80); ll.printList(); int s = ll.getSize(); System.out.println(s); } — madil26, Jul 22 '19 at 23:45
What I'm trying to say is 15 goes into head, then once I push 4, 15 should move to head.next and so forth. It all makes sense in my head. — madil26, Jul 22 '19 at 23:48
Since you haven't update the code, how are we to know what's wrong with the updated version? --- And don't post code in a comment. **Edit** the question to show clarifying information. — Andreas, Jul 22 '19 at 23:50
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Jul 22 '19 at 23:53
@Andreas Still getting used to stack overflow, its been a while. But "What I'm trying to say is 15 goes into head, then once I push 4, 15 should move to head.next and so forth. It all makes sense in my head." — madil26, Jul 23 '19 at 04:32
`if (head == null) { newNode.next = head;` Well, `head` is null, so assigning to `newNode.next` is redundant. --- `else { newNode.next = head.next; head.next = new Node(data);` I think you meant `newNode.next = head; head = newNode`, otherwise the existing head is still the head, and you sure don't want to create two node objects in a single `push` call. --- And *please* format your code for human readability, i.e. **indent** the code to show the program structure. — Andreas, Jul 23 '19 at 04:36
@Andreas Wow! I was clearly over-complicating this. This was exactly what I was looking for. — madil26, Jul 29 '19 at 02:58

Manish Jindal · Answer 1 · 2019-07-22T05:08:03.840

0

The while loops are the causing the infinite loop. The condition tmp!=null won't become false as tmp is staying what it already was. It is not traversing. Same is the case in the second function where head is never traversing forward and hence if it is not null, it will stay not-null and loop won't end.

This will work -

In your push() function -

else{
   Node node = new Node(data);
   node.next = head;
   head.prev = node;   // taking into account that it is a dll
   this.head = node;
   return node;
}

And your insertAtEnd(int data) -

public Node insertAtEnd(int data){
  Node tmp = this.head;
  while(tmp.next!=null){
    tmp = tmp.next;
  }
  tmp.next = new Node(data);
  tmp.next.prev = tmp;    // taking into account that it is a dll
  return tmp.next;
}

P.S. in insertion functions there are generally no returns as we just insert some data into the data-structure. At most we may need whether the insertion was successful or not.

edited Jul 22 '19 at 05:08

answered Jul 22 '19 at 04:33

Manish Jindal

56
5

What about `previous`? – Andreas Jul 22 '19 at 04:37
I assume he might have mistakenly added prev as the member variable. As he mentioned, its a linked list and not doubly linked list. – Manish Jindal Jul 22 '19 at 04:49
The term "linked list" doesn't imply "singly" or "doubly", it can be either, so don't presume OP meant "singly". The field `previous` implies "doubly", and that OP's code is currently missing that part because it's incomplete. We know OP is working on it, since the first part isn't even working yet. – Andreas Jul 22 '19 at 04:52
Yes, understood. Thanks. – Manish Jindal Jul 22 '19 at 04:54

Andrews B Anthony · Answer 2 · 2019-07-22T04:43:07.160

0

You have a unnecessary while loop in the else statement of the push method.

while(temp!=null)

public Node push(int data){
    Node newNode = new Node(data);
    if(head == null){
    newNode.next = head;
    head = newNode;
    }
    else{
    newNode.next = head.next;
    head.next = new Node(data);            
    }        
    return head;
    }

edited Jul 22 '19 at 04:43

answered Jul 22 '19 at 04:34

Andrews B Anthony

1,381
9
27

Why have a `temp` variable? There's no need. – Andreas Jul 22 '19 at 04:36
OP preferred to have. for OP's understanding @Andreas – Andrews B Anthony Jul 22 '19 at 04:37
OP "preferred" that? How do you know? I think it's a lot more likely that OP mistakenly thought it was needed for the `while` loop. – Andreas Jul 22 '19 at 04:41
@Andreas Yes that could be the case. I'll edit. Thanks. – Andrews B Anthony Jul 22 '19 at 04:41
@Andreas I was only using temp because I thought I had to traverse the LL. Now the LL is working but it only displays the first and last Node, but according to my size there is only two Nodes which makes no sense because I have created 4. – madil26 Jul 22 '19 at 23:38

Oleg Cherednik · Answer 3 · 2019-07-22T05:30:20.420

public final class LinkedList {

    private Node head;

    // method name should be clear
    public void addHead(int data) {
        Node node = new Node(data);

        if (!isEmpty())
            updateLinksBeforeInsert(node, head);

        head = node;
    }

    public void addTail(int data) {
        Node node = new Node(data);

        if (isEmpty())
            head = node;
        else
            updateLinksBeforeInsert(findLastNode(), node);
    }

    public boolean isEmpty() {
        return head == null;
    }

    // The last node is the node with 'next == null'
    private Node findLastNode() {
        Node node = head;

        while (node.next != null)
            node = node.next;

        return node;
    }

    // Before insert both 'prev' and 'next' links should be correctly updated
    private static void updateLinksBeforeInsert(Node prev, Node next) {
        prev.next = next;
        next.prev = prev;
    }

    // Accept a stream is more flexible than simple System.out
    public void print(PrintStream out) {
        Node node = head;

        while (node != null) {
            // print '-->' only after the first element
            if (node != head)
                out.print("-->");
            out.print(node.data);
            node = node.next;
        }
    }

    // Node should not be visible outside LinkedList
    private static final class Node {

        final int data;
        Node next;
        Node prev;

        private Node(int data) {
            this.data = data;
        }
    }

I'm trying to visualize a Linked List, I want to insert a Node at the head and push the other node to next

3 Answers3