Win a copy of Transfer Learning for Natural Language Processing (MEAP) this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Paul Clapham
  • Devaka Cooray
  • Bear Bibeault
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Liutauras Vilda
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Piet Souris
Bartenders:
  • salvin francis
  • Carey Brown
  • Frits Walraven

Deleting a Node from a Singly Linked List

 
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was reading a book " cracking the coding interview" wherein I came across the code below : I didn't understand why would i have to return head.next in line 12 ? In line 17 we are returning the head but we are updating Node n, not head. Shouldn't I return n instead of head  ?

 
Bartender
Posts: 7065
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Line 17 is returning after you removed a node from the MIDDLE of the list. So, the head is still the head, only the middle has been modified.
 
Marshal
Posts: 68909
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why would a delete method return a Node in the first place? Shouldn't it be called remove() to match the remove() method in java.util.List? Wouldn't it return the value removed, so its return type would be int? Does that description say anything about the potential inefficiency of iterating a linked list?
 
Saloon Keeper
Posts: 3895
154
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If all you have to go by is the Node head, then you want to have a valid head even if it is the head itself that is being removed. So you should invoke this method with something like:

 
Campbell Ritchie
Marshal
Posts: 68909
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks like non‑object‑oriented code to me. You don't have a linked list object that takes care of itself, so calling code has to take care of it. Sounds like a breach of the S in “SOLID” to me.
 
Marshal
Posts: 25436
65
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Why would a delete method return a Node in the first place? Shouldn't it be called remove() to match the remove() method in java.util.List? Wouldn't it return the value removed, so its return type would be int? Does that description say anything about the potential inefficiency of iterating a linked list?



There aren't any Javadoc comments, so perhaps the requirements are elsewhere. But it looks like all you have for this so-called linked list is a reference to the list's head node. So if you delete a node from the list, that might change the head node, and so you need to know what the (possibly new) head node of the list is after the deletion.
 
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I believe we've seen this design before. If this Node class was encapsulated in a LinkedList class, then managing the head of the list this way wouldn't be too bad. However, if this were a top-level class where client code had to keep a reference to the head of a list, then it's not a very good design, in my opinion. I would even guess that it's something that some instructor took from a non-object oriented language and tried to directly translate it to Java. If that was the case, then the instructor was being lazy at best.
 
Piet Souris
Saloon Keeper
Posts: 3895
154
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Now that we know why head is always returned, a question for OP:

the method "deleteNode" has 'Node head' as one of its arguments. Do you think that argument is necessary? If not, how should the code be changed if it was left out?
 
Campbell Ritchie
Marshal
Posts: 68909
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . If not, how should the code be changed if it was left out?

It would have to be changed to object‑oriented (=OO) code. Taking two parameters makes that a bit of procedural code. The OO way to write that code would be myLinkedList.remove(123); and would return the removed value or would have void instead of a return type.
 
Md Zuanyeed Kamal
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Why would a delete method return a Node in the first place? Shouldn't it be called remove() to match the remove() method in java.util.List? Wouldn't it return the value removed, so its return type would be int? Does that description say anything about the potential inefficiency of iterating a linked list?



page no 93 of 6th edition of this  her book, it was mentioned :

Deleting a node from a linked list is fairly straightforward. Given a node n, we find the previous node prev and set prev. next equal to n. next. If the list is doubly linked, we must also update n. next to set n. next. prev equal to n. prev. The important things to remember are (1) to check for the null pointer and (2) to update the head or tail pointer as necessary.



But I didn't understand it clearly.


[edit]Change green text to quote block.
 
Md Zuanyeed Kamal
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:I believe we've seen this design before. If this Node class was encapsulated in a LinkedList class, then managing the head of the list this way wouldn't be too bad. However, if this were a top-level class where client code had to keep a reference to the head of a list, then it's not a very good design, in my opinion. I would even guess that it's something that some instructor took from a non-object oriented language and tried to directly translate it to Java. If that was the case, then the instructor was being lazy at best.



you can consider the deleteMethod is in different class.



Node deleteNode(Node head, int d) {
Node n = head;

if (n.data == d) {
return head.next; /* moved head*/
}

while (n.next != null) {
if (n.next.data == d) {
n.next = n.next.next;
return head; /* head didn't change*/
}
n = n.next;
}
return head;
}

 
Junilu Lacar
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Md Zuanyeed Kamal wrote:you can consider the deleteMethod is in different class.


Not sure what you mean by that but if I take that statement at face value, that's a horrible design choice.
 
Campbell Ritchie
Marshal
Posts: 68909
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:. . . you need to know what the (possibly new) head node of the list is after the deletion.

Yes, of course you do. But a high‑level solution would have a variable of type linked list and that list variable would retain the reference to the head. The rest of the code shouldn't need to know where the head node is nor whether it changes because the list variable takes care of all that.

[addition]Looking back at prvious posts in this th‍read, I see Junilu's opinion appears to be the same as mine.
 
Campbell Ritchie
Marshal
Posts: 68909
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Md Zuanyeed Kamal wrote:. . . page no 93 of 6th edition of this  her book, . . .

Please supply the author's name.

Please practise drawing the structure of a linked list, and practise writing its simple operations. Make sure to give it a private nested Node class and to maintain references to the head Node. Start with a singly‑linked list and then enhance it to a doubly‑linked list, which has a tail Node as well as a head. Then you will understand what the quote from the book means.

Please use the quote button, not green text; some people can only read certain colours.
 
Piet Souris
Saloon Keeper
Posts: 3895
154
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OP's question was why head.next or head was returned, not whether there would be better suited constructions.
 
Campbell Ritchie
Marshal
Posts: 68909
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you remove the current head node, the head.next node becomes the head.

There is probably an easier and more elegant way to achieve that. Yes, you create a dummy node with the current head as its next field, When you have deleted your one node, then dummy.next is the head of the list, and you can return that. No need for the double return or anything.
 
Piet Souris
Saloon Keeper
Posts: 3895
154
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yep, and so the most interesting question to OP is:

given a Node head and given you want to delete a Node with value 123, what code would you use?
 
Md Zuanyeed Kamal
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Md Zuanyeed Kamal wrote:. . . page no 93 of 6th edition of this  her book, . . .

Please supply the author's name.

Please practise drawing the structure of a linked list, and practise writing its simple operations. Make sure to give it a private nested Node class and to maintain references to the head Node. Start with a singly‑linked list and then enhance it to a doubly‑linked list, which has a tail Node as well as a head. Then you will understand what the quote from the book means.

Please use the quote button, not green text; some people can only read certain colours.



Author: Gayle Laakmann McDowell 6th edition.

I will try to implement a simple singly linklist. lets see, if i can get the concepts.
 
Campbell Ritchie
Marshal
Posts: 68909
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for the author's name: I am not familiar with that book.
Be sure to study the structure of a linked list from diagrams before you try to implement it.
 
Hey, I'm supposed to be the guide! Wait up! No fair! You have the tiny ad!
Two software engineers solve most of the world's problems in one K&R sized book
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
    Bookmark Topic Watch Topic
  • New Topic