as far as I can see, you can do:
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
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;
}
}
currentItem.Next and, if necessary, dispose of currentItem. In this case the previousItem reference is not needed.Delete(1, 2). You will end with the list 2->3->4->5 because the Initial node will not be correctly set. This is because you only modify Initial when previousNode is null. After you've walked over the initial item in the list you will have Initial pointing to the node containing 2, previousNode pointing to the node containing 1 and currentNode pointing to the node containing 2. Thus the next time through the loop previousNode will not be null so Initial will not change. I'll provide a fix.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
Well, you could just use LinkedList<T> and Remove; but manually:
prev.next = node.next
LinkedList<T> however.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;
}
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,
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.
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;
}
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#.
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.
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();
}
Here is a working solution for deleting a node from LinkedList in C#.
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();
}
}
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/
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;
}
}
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
