# Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

Example: If a linkedlist list contains 10->20->30->40, and 2nd node has to be deleted then the output should be 10->30->40

This question is attributed to Geeksforgeeks. Looking for code-review, optimizations and best-practices.

    class Nodde<T> {
Nodde<T> next;
T item;

Nodde(T item) {
this.item = item;
}
}

private Nodde<T> first;
private Nodde<T> last;

this.first = first;
}

@Override
public int hashCode() {
int hashCode = 1;
for (Nodde x = first; x != null; x = x.next)
hashCode = 31*hashCode + (x == null ? 0 : x.hashCode());
return hashCode;
}

@Override
public boolean equals(Object obj) {

if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Nodde<T> currentListNode = first;
Nodde<T> otherListNode =  other.first;

while (currentListNode != null && otherListNode != null) {

if (currentListNode.item != otherListNode.item) {
System.out.println(currentListNode.item);
return false;
}
currentListNode = currentListNode.next;
otherListNode = otherListNode.next;
}

return currentListNode == null && otherListNode == null;
}
}

public final class DeletePtr<T> {

public static <T> void delete(Nodde<T> ptr) {

if (ptr == null) {
throw new IllegalArgumentException("The pointer cannot be null.");
}

if (ptr.next == null) {
throw new IllegalArgumentException("The last node cannot be deleted.");
}

ptr.item = ptr.next.item;
ptr.next = ptr.next.next;
}
}

public class DeletePtrTest {

@Test
public void test1() {
Nodde<Integer> node1 = new Nodde<Integer>(10);
Nodde<Integer> node2 = new Nodde<Integer>(20);
Nodde<Integer> node3 = new Nodde<Integer>(30);
Nodde<Integer> node4 = new Nodde<Integer>(40);
Nodde<Integer> node5 = new Nodde<Integer>(50);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

DeletePtr.delete(node3);

Nodde<Integer> nodeExpected1 = new Nodde<Integer>(10);
Nodde<Integer> nodeExpected2 = new Nodde<Integer>(20);
Nodde<Integer> nodeExpected3 = new Nodde<Integer>(40);
Nodde<Integer> nodeExpected4 = new Nodde<Integer>(50);

nodeExpected1.next = nodeExpected2;
nodeExpected2.next = nodeExpected3;
nodeExpected3.next = nodeExpected4;

assertEquals(llActual, llExpected);
}

@Test
public void test2() {
Nodde<Integer> node1 = new Nodde<Integer>(10);
Nodde<Integer> node2 = new Nodde<Integer>(20);
Nodde<Integer> node3 = new Nodde<Integer>(30);
Nodde<Integer> node4 = new Nodde<Integer>(40);
Nodde<Integer> node5 = new Nodde<Integer>(50);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

DeletePtr.delete(node4);

Nodde<Integer> nodeExpected1 = new Nodde<Integer>(10);
Nodde<Integer> nodeExpected2 = new Nodde<Integer>(20);
Nodde<Integer> nodeExpected3 = new Nodde<Integer>(30);
Nodde<Integer> nodeExpected4 = new Nodde<Integer>(50);

nodeExpected1.next = nodeExpected2;
nodeExpected2.next = nodeExpected3;
nodeExpected3.next = nodeExpected4;

assertEquals(llActual, llExpected);
}
}

-
Nodde instead of Node? Intentional typo??? – h.j.k. Aug 7 '14 at 7:04
I think it's to prevent namespace collisions, but that's not a good excuse. Incoming review... – Pimgd Aug 7 '14 at 7:16
Perhaps you should compare elements with Equals instead of == in your overridden Equals method. – CodesInChaos Aug 7 '14 at 16:15
I can't join chat where I am right now, but this clearly seems to be a beginner-intermediate level programming challenge. Telling the OP to use Java's library is like asking them to skip their data structures and algorithms courses. There is so much they can learn by thinking about and implementing a linked list, even if it's not something you would push into production-level code. – Ryan Aug 7 '14 at 17:59
What was the programming challenge question — this one? If so, the inputs, and therefore the solution, should be quite different. – 200_success Aug 7 '14 at 18:06

I had tagged your question , because you're recreating a LinkedList, and Java already has one. @200_success has removed this tag for some reason, allowing me to post this answer:

There's no reason for you to be writing your own implementation. Using Java's own LinkedList (full classified name: java.util.LinkedList), you can use removeAt(index) to remove a node. If you only have a reference to an object that is contained in the list, you can use remove(Object).

As it stands right now, you expose your nodes to the user of your class. You make THEM manage the LinkedList, whereas the LinkedList itself is nothing but a wrapper. If the user messes up and accidentally points the last node to another node, then makes a clone and compares them with equals or ==, the program will get into an infinite loop. If someone inserts a LinkedList which has the last node point to another node into something like a HashMap, the program will get into an infinite loop.

Searching for an element in the list requires the user to built their own implementation of a search function. In fact, doing anything with the list (other than removing an element) requires the user to get their hands dirty.

But lets say I wanted to use this LinkedList for a valid purpose. I can't even remove the last node from the LinkedList. That could significantly limit my options.

Actually, removing itself is rather dirty because you've called it delete. This gives me certain assumptions - namely, that the object won't exist anymore after I have called the function.
I call delete(Node) and surprise surprise... the node still exists! Except it has different values now. This means you're altering the objects I'm holding in my hands. You're even altering the objects you're holding in your own hands - in the first and last fields.

There's another bug related to that: When I make a list of 2 Nodes, and I remove the first one, you end up having a LinkedList that contains 1 node... double! And if I were to add another node with a different item in it, last wouldn't even point to the proper node!

When you combine all these reasons, you should see that it is a bad idea to reinvent the wheel. Just use Java's LinkedList and the methods they provide. That way you don't have as much bugs, you don't force the user to make their hands dirty, you don't have to test whether your list works, and you give your user more freedom in how they can use the list.

-
I was going to downvote this (for saying "just use LinkedList" on what looks like a data structures assignment or challenge) then I remembered I was on codereview. – immibis Aug 7 '14 at 9:26
There are occasionally reasons to reimplement singly linked lists. The best case that I see is for tail sharing (which sometimes tends to suggest immutability, too). This question doesn't seem to use that functionality, though, so I think this advise of "just use Java's list" makes sense here. – Joshua Taylor Aug 7 '14 at 14:56
I have nothing against building your own implementation of LinkedList. ... but if you are gonna do it, then you need to be really sure that doing it yourself is the best course of action. – Pimgd Aug 7 '14 at 14:59
-1 for writing a several paragraph post telling them to use LinkedList when the OP was doing a coding exercise – Winston Ewert Aug 7 '14 at 17:28
My bad, please edit your post so I can remove my downvote. – Winston Ewert Aug 7 '14 at 17:36

Here:

        for (Nodde x = first; x != null; x = x.next)
hashCode = 31*hashCode + (x == null ? 0 : x.hashCode());


inside the loop you know that x!=null so no need for ternary operator.

-

## Nodde

For starters, as others have mentioned it seems odd to have your node named Nodde. If you have a valid reason for this, that's great, but it should probably be renamed as Node. As Pimgd noted in their comment, this might be indicative of namespace collisions. In Java, we avoid namespace collisions through packages. I suggest, even for simple projects like this, to use packages. I have a test project and its package is com.me.testing.

Also, its Node<T> should be nested. See this page for a guideline on doing that in Java. Doing this will completely close out the outside world from knowing what you're doing underneath, which is a good thing. This hides the implementation.

Additionally, you should make the constituent pieces of the node private. Exposing the underlying implementation is almost always a bad code smell and poor practice. In this case, it probably makes sense to have setters and getters for both next and item, which makes private kind of moot anyway, but it's good to get into the habit of hiding class members, as well as always providing the access modifiers (public, protected, private, etc). Even if your intended access level is the same as the language's default, it's a good thing to explicitly state, because it tells your future self that you thought about, and came to the conclusion, that your access modifier should be public or private, etc.

## Outside of LinkedList; DeletePtr

There's some red flags in DeletePtr. The first is that it exists at all (no offense intended here!). The problem is that DeletePtr is making important decisions about another class - LinkedList - and it should not be able to make those decisions. This creates a very high coupling between the two classes, when in fact the 'delete' routine should just be part of LinkedList. LinkedList is the owner of the data structure, and therefore should have control over adding or removing nodes.

Also, carrying around the idea of "pointer" is something Java discourages. As Pimgd noted, delete has other connotations to it and remove is perhaps a better word for what you're doing (well, it is used by Java's LinkedList, after all).

Another concern is not being able to delete the last node. If I have the list 10->20->30->40 and ask for the 40 to be removed, should it not become 10->20->30? Your removal of a node is a bit flawed for this reason, but we can fix that soon...

## LinkedList

First of all: adding nodes. Currently, you let your users of the LinkedList add nodes however they see fit. This is bad, because your user is a monkey at a keyboard and will do stupid things. (This is true even if the only user of your code is you. Trust no one!) To prevent them from sticking their hands where they don't belong, we can add an add method to LinkedList, like so:

public void add(T item) {
if (null != item) {
if (null == first){
first = new Node<T>(item);
}
else if (null == last) {
last = new Node<T>(item);
first.setNext(last);
}
else
{
Node<T> newLast = new Node<T>(item);
last.setNext(newLast);
last = newLast;
}
}
}


Note that this doesn't expose Node to the user. Instead, the user can add an item of type T.

Also, we can move the functionality of DeletePtr into LinkedList. We'll call it remove. This is entirely new code that doesn't reflect what DeletePtr was doing.

public void remove(T item) {
if (item == first.getItem()) {
first = first.getNext();
}

Node<T> curr = first;
while (null != curr) {
if(curr.getNext() != null
&& curr.getNext().getItem() == item) { // Check the *next* node
curr.setNext(curr.getNext().getNext());
}

curr = curr.getNext();
}

if (null == first) {
last = null;
}
}


That function may look confusing, but it will be better if you can draw out what it's doing on paper. A few notes:

• You can remove both the first and last nodes.
• No exceptions. Exceptions should only occur when exceptionally bad things happen. Is attempting to add null to a list exceptional? Maybe, but most likely not. Appending null onto a list should have no effect on the list.
• It checks references. Again, Java eschews the idea of pointers. An object is 'deleted' or 'freed' when it is no longer being referenced.
• The loop is a typical linked-list loop, but slightly modified because it's looking one node ahead. When the next node is the node we want to 'remove' we simply assign the current node's next to the next node's next. In C/C++ this would leave an object hanging in memory, and be called a memory leak. In Java, an object is automatically released by the garbage collector when it is no longer being referenced anywhere else (a bit of a simplification, but you can read up on the GC elsewhere for more detail). It's still a potential vector for memory leaks.

## Equality

For checking equality, there are improvements to be made. Here is a good question that explains what's going on. How you check for equality is up to you, but if you're able to do it in a way that's agnostic to the type of the generics, all the better.

## Constructor

The constructor that takes an item is a bit flawed. By assigning the item to first and last, you're essentially saying that there are now two values in the list. However, first doesn't point to last yet, so only the first one will be seen if you traverse the list. It would be best to simply assign last to null until you have something better to put there(the second node). For the code below, I simply removed that constructor.

## Conclusion

This isn't a perfect LinkedList, obviously, but it's a step in the right direction. As Pimgd said, if you ever have the choice between writing your own version of something and using a tested and vetted library, choose the library. Java's LinkedList has been written, analyzed, studied, and benchmarked by very smart people whose goal was to optimize the functionality therein. Unless you can pinpoint an area where your implementation needs to be faster, it's best to use a library's version. My 1.5 hours of writing code + explaining it is not bullet proof, and certainly nowhere near as robust as the built in library's code.

The full class, without hashCode and equals (which I didn't touch):

public class LinkedList<T>
{
static class Node<T> {
private Node<T> next;
private T item;

public Node(T item) {
this.item = item;
}

public T getItem() {
return item;
}

public Node<T> getNext() {
return next;
}

public void setNext(Node<T> node){
next = node;
}
}

private Node<T> first;
private Node<T> last;

first = null;
last = null;
}

if (null != item) {
if (null == first){
first = new Node<T>(item);
}
else if (null == last) {
last = new Node<T>(item);
first.setNext(last);
}
else
{
Node<T> newLast = new Node<T>(item);
last.setNext(newLast);
last = newLast;
}
}
}

public void remove(T item) {
if (item == first.getItem()) {
first = first.getNext();
}

Node<T> curr = first;
while (null != curr) {
if(curr.getNext() != null && curr.getNext().getItem() == item) {
curr.setNext(curr.getNext().getNext());
}

curr = curr.getNext();
}

if (null == first) {
last = null;
}
}
....
}

-
"because your user is a monkey at a keyboard and will do stupid things" This warrants a second upvote. Good review. – Pimgd Aug 7 '14 at 18:25

Besides the slightly odd class name Nodde (nothing wrong), one suggestion I can make is to use some sort of a builder (or "fluent"?) pattern to construct your linked lists... Possibly along the lines of:

<T> LinkedList<T> createList(T... elements) {
// assume elements is validated
Nodde<T> lastNode = new Nodde<>(elements[elements.length - 1]);
for (int i = elements.length - 2; i >= 0; i--) {
Nodde<T> currentNode = new Nodde<>(elements[i]);
currentNode.next = lastNode;
lastNode = currentNode;
}