CODEWITHSUNDEEP
javalinked-listnodes
Drewvy22
Drewvy22

Reputation: 39

Setting Current Node to Null?

I've been practicing problems on Cracking the Coding Interview and I came up with a solution to a problem asking to remove a middle node in a linked list.

 public void deleteMidNode(Node mid){
    if(mid == head || mid.next==null){
        return;
    }
    Node current = mid;
    while(current.next.next!=null){
        current.data = current.next.data;
        current = current.next;
    }
    current.next = null;
}

Now this code does work - I've tested it. However, I'm curious as to why I can set current.next to null, but if I was to do this it doesn't work:

 public void deleteMidNode(Node mid){
    if(mid == head || mid.next==null){
        return;
    }

    Node current = mid;
    while(current.next!=null){
        current.data = current.next.data;
        current = current.next;
    }
    current = null;     
}

Can anyone tell me why I can't set a current node to null?

Upvotes: 1

Views: 8730

Answers (4)

Sarwan
Sarwan

Reputation: 657

I don't get it why it is not giving the compilation error first of all for the below code:

current = current.next;

This should give compilation error, since you are assigning a node pointer to a node.

When I run the same function while passing the pointer it works.

#include<stdio.h>
#include<malloc.h> // C library to handle malloc functions

struct node{ // struct node declaration
    int data;
    struct node* link;
};
void deleteNode(struct node*);
void printList(struct node*);
int main(){
    struct node* head;
    struct node* first;
    struct node* second;
    struct node* third;
    struct node* fourth;
    struct node* fifth;
    struct node* sixth;
    head = (struct node*)malloc(sizeof(struct node));
    first = (struct node*)malloc(sizeof(struct node));
    second = (struct node*)malloc(sizeof(struct node));
    third = (struct node*)malloc(sizeof(struct node));
    fourth = (struct node*)malloc(sizeof(struct node));
    fifth = (struct node*)malloc(sizeof(struct node));
    sixth = (struct node*)malloc(sizeof(struct node));
    head->link = first;
    first->link = second;
    second->link = third;
    third->link = fourth;
    fourth->link = fifth;
    fifth->link = sixth;
    sixth->link = NULL;
    head-> data = 1; 
    first-> data = 2;
    second-> data = 3;
    third-> data = 4;
    fourth-> data = 5;
    fifth-> data = 6;
    sixth-> data = 7;
    printList(head);
    deleteNode(second);
    printList(head);
}
void printList(struct node* head){
    struct node* node = head;
    while(node->link!= NULL){
        printf("%d\n",node->data);
        node= node->link;
    }
}
void deleteNode(struct node* kid){
    struct node* mid = kid;
    while(mid->link!= NULL){
        mid->data = mid->link->data;
        mid = mid->link;
    }
    mid = NULL;
}

Upvotes: 0

cadolphs
cadolphs

Reputation: 9647

Is your list doubly-linked? In that case, you can just do 

if (mid != null) {
    mid.prev.next = mid.next
    mid.next.prev = mid.prev
}

and let garbage collection do its magic.

In any case, to answer your question, realize that variables for objects (such as Node) in Java are always references (pointers).

In your function, current is a variable that points to a Node object. If you set it to null, it doesn't point anywhere. But that doesn't change the structure of the list.

Upvotes: 1

hardus
hardus

Reputation: 11

If it's a double linked list we need to just link mid.pre to mid.next, if it's singleLinked List we need to traverse from beginning to mid (we need previous node Prv.next = mid) and just replace prv.next = mid.next.

Question: In both of your solutions how can we traverse from head after removing mid Node?

Upvotes: 1

weston
weston

Reputation: 54801

To answer your question, because it's an example of dead code. It's a local variable, so as the final write to it is not later read by any code, it will have no effect on the program.

That is:

    current = null;
    //there are no reads of "current" here before:
} //the end of method which is the end of scope for the local "current"

A decent IDE would be hinting to you that this write was not read, by, for example, graying out, underlining or otherwise highlighting the dead code.

I don't think it's worth analyzing your code too closely though as it's totally wrong I'm afraid, removing an item from a linked list should be a O(1) constant time procedure (at least once you have the node and previous node located). You are moving the data around, causing it to be O(n), meaning it's no more efficient than removing from an array of data.

Given this:

node1 -> node2 -> node3 -> node4
  |        |        |        |
data1    data2    data3    data4

Removing node2, should go to:

node1 -> node3 -> node4
  |        |        |
data1    data3    data4

But you move the data around as though shuffling items along in an array. This causes it to be:

node1 -> node2 -> node3
  |        |        |
data1    data3    data4

current.data should never need to be reassigned for any linked list operation.

Upvotes: 1

Related Questions