Îndepărtarea nodului din lista legată unică (Programare, C#, Listă Legată)

CasperT a intrebat.

din câte văd eu, poți face:

  1. Găsiți nodul care trebuie eliminat.
  2. node.previous.next = node.next
  3. node.next.previous = node.previous
  4. node.previous = null
  5. node.next = null
  6. Eliminați nodul dacă vă aflați într-un mediu anon-GC

Dacă lista dvs. este o listă dublu legată.

Dar cum faci asta cu o listă cu o singură legătură?Am încercat o mulțime de lucruri, fără succes :(Pur și simplu fac să elimine un anumit index sau nu face nimic deloc.

13 răspunsuri
jason

Începeți de la începutul listei. Mențineți o referință la elementul curent (currentItem) și la elementul anterior (previousItem). Căutați liniar elementul pe care doriți să îl eliminați, mergând întotdeauna cu previousItem = currentItem, currentItem = currentItem.Next. În cazul în care elementul pe care doriți să îl eliminați este capul de listă, realocați capul de listă la currentItem.Next. În caz contrar, setați previousItem.Next = currentItem.Next. Dacă este necesar (după cum spuneți, într-un mediu non-GC), eliminați currentItem.

Practic, utilizați previousItem pentru a imita comportamentul unui currentItem.Previous în cazul unei liste cu două legături.

Editare: Aceasta este o implementare corectă a 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;
    }
}

Comentarii

  • Este inteligent! Nu mă gândisem la mimare! Deși, nu pare să funcționeze, dacă elementul este primul element din lista mea? –  > Por CasperT.
  • @CasperT: Dacă elementul este chiar primul din listă, trebuie doar să realoci capul listei către currentItem.Next și, dacă este necesar, se elimină currentItem. În acest caz previousItem referință nu este necesară. –  > Por jason.
  • Cred că m-am îndepărtat puțin de la subiect. Mi-am actualizat întrebarea 🙂 –  > Por CasperT.
  • Oh și, de asemenea, dacă elementul se află la sfârșitul listei mele – nu va funcționa nici el 🙂 –  > Por CasperT.
  • @CasperT: Ceea ce ați furnizat nu va funcționa. Luați în considerare 1->2->3->4->5 și apelarea Delete(1, 2). Veți sfârși cu lista 2->3->4->5 deoarece Initial nod nu va fi setat corect. Acest lucru se datorează faptului că modificați doar Initial atunci când previousNode este null. După ce ați trecut peste elementul inițial din listă veți avea Initial indicând nodul care conține 2, previousNode indicând spre nodul care conține 1 și currentNode indicând spre nodul care conține 2. Astfel, la următoarea trecere prin buclă previousNode nu va fi null atât de Initial nu se va schimba. Voi oferi o soluție. –  > Por jason.
Heiko Hatzfeld

Țineți evidența ultimului nod în timp ce încercați să găsiți „nodul curent”.

Apoi, puteți conecta anterioruse.next la current.next și ați terminat.

Comentarii

  • Nu pare să funcționeze dacă elementul (elementele) dorit(e) se află fie la sfârșitul, fie la începutul listei –  > Por CasperT.
Marc Gravell

Ei bine, ați putea folosi pur și simplu LinkedList<T> și Remove; dar manual:

  • iterați înainte până când găsiți nodul pe care doriți să-l eliminați păstrând nodul anterior disponibil într-o variabilă în fiecare punct
  • set prev.next = node.next
  • du-te acasă

Comentarii

  • Ar trebui să verificați dacă prev este nulă, nu-i așa? –  > Por vpram86.
  • a numi LinkedList<T> „agnostic de limbaj” ar fi un pic cam exagerat 😉 –  > Por HerdplattenToni.
  • @HerdplattenToni – verificați istoricul de editare; a fost C# la un moment dat! –  > Por Marc Gravell.
  • @Marc Gravell: Am făcut editarea pentru că prima versiune a postării sale părea să caute ideea și nu codul într-un limbaj specific (așa cum indica și ghidul său despre cum să o facă pentru o listă dublu-legată). Acum că a adăugat codul, am adăugat din nou eticheta. Se pare că nu folosește LinkedList<T> totuși. –  > Por jason.
alex

Următorul cod folosește recursivitatea pentru a ține evidența nodului anterior: Sursa: 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;
}

Bragaadeesh

Puteți găsi implementarea completă a Listei legate singure cu toate funcțiile precum Add, Remove, InsertAt etc., aici.http://tech.bragboy.com/2010/01/linked-lists.htmlNotă: Aceasta are un cod Java funcțional + clase de testare, astfel încât să nu vă lipsească nimic din ceea ce reprezintă o listă legată singular,

Tor Haugen

Aceasta este principala slăbiciune a listei cu legături simple. Va trebui fie să aveți o referință la nodul anterior, fie să parcurgeți lista de la început.

RvdK

țineți minte ultimul nod în care ați fost.

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

Comentarii

  • Nu sunt sigur cum ați putea implementa un foreach 🙂 –  > Por CasperT.
mpen

Aproape ironic că tocmai ai întrebat asta. Și eu încerc să mă perfecționez în materie de liste legate individual. Tocmai am scris această funcție în C++ care pare să funcționeze:

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

Pentru a scoate ultimul element, dar o poți modifica ușor pentru a funcționa la mijloc, sunt sigur. Ideea este cam aceeași și în C#.

Comentarii

  • Bună, am scris o funcție pop() mai devreme astăzi. pastebin.com/m7bd8ca12 Pare să funcționeze și este mult mai scurt 🙂 totuși are nevoie de un null validat –  > Por CasperT.
  • Ei bine, asta face pop la primul element. Al meu îl scoate pe ultimul… nu la fel de ușor. –  > Por mpen.
  • Oh, bine, îmi tratez lista ca pe o stivă 🙂 Nu am observat asta –  > Por CasperT.
Abhishek Hariharan
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;
}

Acest lucru ar trebui să funcționeze pe majoritatea sistemelor de operare, în opinia mea.

utilizator2047581
    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();
    }

Rajesh Mishra

Iată o soluție de lucru pentru ștergerea unui nod din LinkedList în C#.

  • În primul rând, Looping prin noduri până când găsim nodul corespunzător.
  • În al doilea rând, se actualizează valoarea Nodului anterior și a Nodului curent.
  • În cazul în care primul nod, adică nodul anterior, este nul, se îndreaptă capul către nodul următor.

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

maxspan

Pentru a elimina un anumit nod dintr-o listă legată unică pe baza valorii indexului elementului din listă. Codul de mai jos este următorul

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

Codul complet poate fi găsit pe http://fumycoder.com/2017/09/06/linked-list/

Radu094

În TEORIE, ați putea face acest lucru pentru a elimina orice nod aleatoriu dintr-o listă de legături unică:

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

}

Dar, trebuie să aveți grijă la problemele de concurență. (de exemplu, dacă altcineva are o legătură cu nodul tău, presupunând că acesta încă mai poartă vechea valoare (o problemă ABA) ), și trebuie să ai un nod „marker” (gol) la sfârșitul listei, pe care nu trebuie să încerci niciodată să îl ștergi (din cauza toRemove.next.next).

Edit: evident, PointerToSomeValue este orice date pe care doriți să le păstrați în listă. Și nu ștergeți de fapt nodul, ci practic eliminați următorul nod din listă, oh, ei bine… ați prins ideea