Remove node from single linked list.

Question

Hi, as far as I can see, you can do:

1. Find the node to remove.
2. node.previous.next = node.next
3. node.next.previous = node.previous
4. node.previous = null
5. node.next = null
6. Dispose of node if you're in a non-GC environment

If your list is a double linked.

But how do you do it with a single linked list? I have tried a lot of things, with no avail :( I simply get it to remove a specific index instead or it does nothing at all

Answer 1

Start at the beginning of the list. Maintain a reference to the current item (currentItem) and the previous item (previousItem). Linearly search for the item that you want to remove always walking with previousItem = currentItem, currentItem = currentItem.Next. If the item that you want to remove is the head of the list, reassign the head of the list to currentItem.Next. Otherwise, set previousItem.Next = currentItem.Next. If necessary (as you say, in a non-GC environment) dispose of currentItem.

Basically you are using previousItem to mimic the behavior of a currentItem.Previous in the case of a doubly-linked list.

Edit: This is a correct implementation of Delete:

public void Delete(int rangeStart, int rangeEnd) {
    Node previousNode = null, currentNode = Head;
    while (currentNode != null) {
        if (currentNode.Data >= rangeStart && currentNode.Data <= rangeEnd) {
            if (previousNode == null) {
                Initial = currentNode.Next;
            }
            else {
                previousNode.Next = currentNode.Next;
            }
        }
        else {
            previousNode = currentNode;
        }
        currentNode = currentNode.Next;
    }
}

Answer 2

You keep track of the last node while you try to find the "current node".

Then you can wire up the previouse.next to current.next and you are done

Answer 3

The following code uses recursion to keep track of previous node: Source: http://www.cs.bu.edu/teaching/c/linked-list/delete/

nodeT *ListDelete(nodeT *currP, elementT value)
{
  /* See if we are at end of list. */
  if (currP == NULL)
    return NULL;

  /*
   * Check to see if current node is one
   * to be deleted.
   */
  if (currP->element == value) {
    nodeT *tempNextP;

    /* Save the next pointer in the node. */
    tempNextP = currP->next;

    /* Deallocate the node. */
    free(currP);

    /*
     * Return the NEW pointer to where we
     * were called from.  I.e., the pointer
     * the previous call will use to "skip
     * over" the removed node.
     */
    return tempNextP;
  }

  /*
   * Check the rest of the list, fixing the next
   * pointer in case the next node is the one
   * removed.
   */
  currP->next = ListDelete(currP->next, value);


  /*
   * Return the pointer to where we were called
   * from.  Since we did not remove this node it
   * will be the same.
   */
  return currP;
}

Answer 4

Well, you could just use LinkedList<T> and Remove; but manually:

• iterate forwards until you find the node you want to remove keeping the previous node available in a variable at each point
• set prev.next = node.next
• go home

Answer 5

keep remebering the last node you been too.

//PSEUDO CODE

Node prevnode = null;
foreach (node n in nodes)
{
    if (n.name.equals(name))
    {
     if (prevnode != null)
     {
      prevnode.next = n.next;
     }
     remove n;
     break;
    }

    prevnode = n;
}

Answer 6

This is the primary weakness of the singly-linked list. You'll either need to have a reference to the previous node, or scan through the list from the beginning.

Answer 7

In THEORY, you could do this to remove any random node from a single link list:

void RemoveNode(Node toRemove)
{
    toRemove.PointerToSomeValue = toRemove.NextNode.PointerToSomeValue ;
    toRemove.NextNode = toRemove.NextNode.NextNode ;

}

But, you need to be carefull about concurency issues. (ie. somebody else has a link to your node assuming it still caries the old value (an ABA problem) ), and you need to have a "marker" (empty) node at the end of the list, which you must never attempt to delete.(because of the toRemove.next.next)

Edit: obviously PointerToSomeValue is whatever data you want to keep in your list. And you're not actually deleting the node, you're basically removing the next node in the list, oh,well.. you get the ideea

Answer 8

Almost ironic you should just ask this. I'm trying to brush up on my singly linked lists too. I just wrote this function in C++ that seems to work:

void pop_back() {
    if(head == NULL) {
        return;
    }

    if(head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }

    Node *iter = head;
    while(iter->next->next != NULL) {
        iter = iter->next;
    }
    delete iter->next;
    iter->next = NULL;
}

For popping the last element, but you can modify it slightly to work in the middle, I'm sure. Idea is pretty much the same in C#.

Answer 9

You may find the comprehensive implementation of Singly Linked List with all the functions such Add, Remove, InsertAt etc., here. http://technicalypto.blogspot.com/2010/01/linked-lists.html Note: This has a working Java code + Test classes so that you would not miss out on anything that a singly linked list is made of,

Answer 10

struct node_t {

int data;
struct node_t *next;

}

void delete_node( struct node_t *random) {

struct node_t *temp;

/* Save the ptr to the next node */
temp = random->next;

/* Copy stuff from the next node to this node */
random->data = random->next->data;
random->next = random->next->next;

/* Delete the next node */
free (temp);

return;

}

This should work on most Operating Systems in my opinion.