0

I am having some trouble understanding why the function delete() below works for deleting a node in a linked list. I abridged the rest of the code to make this all easier to read.

So, I understand we have a node first with a bunch of nodes linked to first. I also understand that in the delete() function, we need to create a new node n to traverse the list. Here's my hang up:

If we create a new node n, and set n = first, we've created a new node, and the node constructor defines that n will have a new node n.next as well. So, haven't we created a whole new list, separate from the list that begins with first? When the delete() function gets to the point where it sets n.next = n.next.next, isn't that deleting a node in a whole separate list of n nodes? How does this delete the node that is linked off of first? Conceptually, this is my hang up.

How are we actually deleting the node in the list that begins with first?

Edit: I think maybe I answered my own question but I was hoping someone could verify. Does this work because both the first and n nodes are actually just references back to the New Node() object created in the Add() function? When I learned programming it was with C++ so I'm used to seeing pointers, and this code didn't make much sense; but as I understand it Java doesn't explicitly have pointers... so am I correct about all of this?

public class LinkedList { static class Node { public Node() { } public double item; public Node next; } int N; Node first; public LinkedList () { first = null; N = 0; public void delete (int k) { if (k == 0) { first = first.next; N--; } else { Node n = first; for (int i = 0; i < k-1; i++) { n = n.next; } n.next = n.next.next; N--; } } public void add (double item) { Node newfirst = new Node (); newfirst.item = item; newfirst.next = first; first = newfirst; N++; } private static void testDelete () { MyLinked b = new MyLinked (); b.add (1); print ("singleton", b); b.delete (0); print ("deleted", b); for (double i = 1; i < 13; i++) { b.add (i); } print ("bigger list", b); b.delete (0); print ("deleted at beginning", b); b.delete (10); print ("deleted at end", b); b.delete (4); print ("deleted in middle", b); } public static void main (String args[]) { testDelete(); } }
Improve this question
3
  • This question is far too broad - in fact, I count at least three different questions here. I recommend running this either in your favourite debugger or on a piece of paper, and narrow your post down to a single question. Commented Jan 29, 2018 at 22:01
  • Java doesn't explicitly have pointers, because everything is a pointer (more correctly, everything except primitive types are references), so yes. This works because they are references. Commented Jan 29, 2018 at 22:06
  • @JoeC I'm sorry if it seemed to broad. I was trying to understand how creating a new node "n" to traverse the list, and then deleting one of the "n" nodes had any effect the originally created list of nodes. But "n" isn't actually a new node, it's just a new reference back to the originally instantiated node, correct? I'm new to Eclipse so running it in the debugger was still confusing, but I think I get it now, thank you! Commented Jan 29, 2018 at 22:23

1 Answer 1

Reset to default
2

This is because each linked list node simply contains a reference to your object and a reference to the next node. In order to delete a node, you simply need to make the previous node point to the one after it.

ie. Initial list:

linkedList ↓ node0 -> node1 -> node2 -> node3

1) If you then were to remove node1, then it'd look like this

linkedList ↓ node0 ----------> node2 -> node3 node1 ----↑

node0 would no longer point to node1, so if you tried to iterate from node0 you'd go to node2 next. However, node1 would still "point" to node2 (until it's garbage collected of course).

2) If you instead removed node0, it look like this:

 linkedList ↓ node0 -> node1 -> node2 -> node3

You simply move the first field of the LinkedList to point to node1 and so, if you were to do linkedList.first you'd be accessing node1. node0 however will eventually get garbage collected because nothing references it (unless you do that somewhere else).

Keep in mind that these cases are true for a singly-linked LinkedList. If you had a doubly-linked LinkedList then, the detaching and reattaching becomes a bit more complicated.

--

I think you have a misunderstanding of what "delete" does. In Java, users don't manually manage memory, so you don't call malloc or delete, destroy, etc. You simply remove all references to the object and they will eventually get garbage collected by the JVM.

In the above code, we're simply talking about "deleting" a Node from a LinkedList in terms of data structures.

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

2 Comments

I understand that we're not explicitly deleting the node object, and that we're just linking the node before to the next one, which essentially loses the object to be deleted. My hangup was the fact that the node n used to traverse the list seemed to create a whole different list of nodes, and I didn't understand how "deleting" a node from that list affected the original list. But n is just a reference back to the original object so that's how it works, right? Thanks!
Yep, n's just a reference to the nodes as you traverse down the list and since it's defined within a function, it only ever lives on the stack anyways.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.