CODEWITHSUNDEEP
c#linked-list
CasperT
CasperT

Reputation: 3475

Remove node from single linked list

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

Upvotes: 4

Views: 31977

Answers (14)

Ivan Petrov
Ivan Petrov

Reputation: 4545

If you have "good taste" you could probably appreciate this solution that relies on ref locals to mimic pointer magic.

public void Remove(T value) {

    ref var indirect = ref _head;
    
    while (indirect != null) {
        if (EqualityComparer<T>.Default.Equals(indirect.Value, value)) {
            indirect = indirect.Next;
            return;
        }
        indirect = ref indirect.Next;
    }
}

Upvotes: 0

maxspan
maxspan

Reputation: 14177

To Remove a particular Node from a Single LinkedList based on the index value of the List item. Below is the code

 public void DeleteNode(int nodeIndex)
    {
        int indexCounter = 0;
        Node TempNode = StartNode;
        Node PreviousNode = null;
        while (TempNode.AddressHolder != null)
        {
            if (indexCounter == nodeIndex)
            {
                PreviousNode.AddressHolder = TempNode.AddressHolder;
                break;
            }
            indexCounter++;
            PreviousNode = TempNode;
            TempNode = TempNode.AddressHolder;
        }
    }

Complete Code can be found on http://fumycoder.com/2017/09/06/linked-list/

Upvotes: 0

Rajesh Mishra
Rajesh Mishra

Reputation: 446

Here is a working solution for deleting a node from LinkedList in C#.

  • First, Looping through nodes till we find the matching node.
  • Second, update Previous Node and Current Node value.

  • If First Node, i.e. previous node is null, point Head to Next Node.

    class LinkedList
{
    private Node Head { get; set; } = null;

    public void Insert(int d)
    {
        Console.WriteLine("Insert : " + d);
        var newNode = new Node() { Data = d, Next = null };
        if (Head == null)
        {
            Head = newNode;
        }
        else
        {
            newNode.Next = Head;
            Head = newNode;
        }
    }

    public void Delete(int d)
    {
        Console.WriteLine("Delete : "+d);
        var node = Head;
        Node currNode = Head;
        Node prevNode = null;
        while (node != null)
        {
            currNode = node;
            if (node.Data == d)
            {
                if(prevNode != null)
                {
                    prevNode.Next = currNode.Next;
                }
                else
                {
                    Head = Head.Next;
                }
                break;
            }
            prevNode = currNode;
            node = node.Next;
        }
    }

    public void Print()
    {
        var list = Head;
        Console.Write("Elements: ");
        while (list != null)
        {
            Console.Write(list.Data + " ");
            list = list.Next;
        }
        Console.WriteLine();
    }
}

Upvotes: 0

Bragaadeesh
Bragaadeesh

Reputation: 21

You may find the comprehensive implementation of Singly Linked List with all the functions such Add, Remove, InsertAt etc., here. http://tech.bragboy.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,

Upvotes: 2

user2047581
user2047581

Reputation: 1

    static void Main(string[] args)
    {
        LinkedList<string> ll = new LinkedList<string>();

        ll.AddLast("uno");
        ll.AddLast("dos");
        ll.AddLast("tres");

        ll.Remove(ll.Find("uno")); // Remove

        foreach (string item in sl)
        {
            Console.WriteLine(item);
        }

        Console.ReadKey();
    }

Upvotes: 0

Abhishek Hariharan
Abhishek Hariharan

Reputation: 1

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.

Upvotes: 0

mpen
mpen

Reputation: 282895

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#.

Upvotes: 0

jason
jason

Reputation: 241641

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;
    }
}

Upvotes: 11

Radu094
Radu094

Reputation: 28424

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

Upvotes: -1

RvdK
RvdK

Reputation: 19790

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;
}

Upvotes: 1

Tor Haugen
Tor Haugen

Reputation: 19627

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.

Upvotes: 1

Marc Gravell
Marc Gravell

Reputation: 1062915

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

Upvotes: 3

alex
alex

Reputation: 75985

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;
}

Upvotes: 2

Heiko Hatzfeld
Heiko Hatzfeld

Reputation: 3197

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

Upvotes: 5

Related Questions