Was ist eine verknüpfte Liste? Was ist der Unterschied zwischen verknüpfter Liste und Array?

Zusammenstellung des zugehörigen Wissens über verknüpfte Listen

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine nicht kontinuierliche und nicht sequentielle Speicherstruktur auf einer physischen Speichereinheit. Die logische Reihenfolge Die Reihenfolge der Datenelemente wird durch die verknüpfte Liste implementiert. Eine verknüpfte Liste besteht aus einer Reihe von Knoten (jedes Element in der verknüpften Liste wird als Knoten bezeichnet), und Knoten können zur Laufzeit dynamisch generiert werden. Jeder Knoten besteht aus zwei Teilen: Einer ist das Datenfeld, in dem Datenelemente gespeichert werden, und der andere ist das Zeigerfeld, in dem die Adresse des nächsten Knotens gespeichert wird.

Der Unterschied zwischen verknüpften Listen und Arrays

Erinnern Sie sich an das Konzept von Arrays. Das sogenannte Array ist eine Sammlung von Elementen desselben Datentyps, die in einer bestimmten Reihenfolge angeordnet sind. Gemäß dem Konzept können wir wissen, dass Arrays im Speicher kontinuierlich sind und verknüpfte Listen aufgrund unterschiedlicher Speichermethoden statisch und verknüpfte Listen dynamisch Speicher zuweisen Da Arrays im Speicher kontinuierlich sind, können wir zum Auffinden Indizes verwenden. Die zeitliche Komplexität beim Auffinden von Elementen in der verknüpften Liste beträgt jedoch O(n). Kontinuität des Arrays, die zeitliche Komplexität des Einfügens oder Löschens von Elementen aus dem Array beträgt O(n) und die zeitliche Komplexität der verknüpften Liste beträgt O(n). Zusammenfassend ist der Unterschied zwischen Arrays und verknüpften Listen wie folgt:
1. Arrays weisen Speicher statisch zu, und verknüpfte Listen weisen Speicher dynamisch zu
2. Arrays sind im Speicher kontinuierlich und verknüpfte Listen sind diskontinuierlich
3. Array-Elemente befinden sich im Stapelbereich und verknüpfte Listenelemente befinden sich im Stapelbereich im Heap-Bereich
4. Die zeitliche Komplexität der Array-Positionierung beträgt O(1) unter Verwendung von Indizes und die zeitliche Komplexität der Lokalisierung von Elementen in verknüpften Listen ist O(n);
5. Die Zeitkomplexität des Einfügens oder Löschens von Elementen aus Arrays ist O(n), die Zeitkomplexität der verknüpften Liste ist O(1).

C# implementiert die Grundoperationen verknüpfter Listen

Am Beispiel einer einfach verknüpften Liste definieren wir gemäß der Definition einer verknüpften Liste zunächst die Datenstruktur der verknüpften Listenknoten

    public class Node<T>
    {
        private T data;
        private Node<T> next;

        //有参构造函数
        //主要用例实例化需要处理的节点用
        public Node(T item, Node<T> next)
        {
            data = item;
            this.next = next;
        }

        //无参构造函数，用例实例化Node节点
        public Node()
        {
            data = default(T);
            next = null;
        }

        public Node<T> Next
        {
            get { return next; }
            set { this.next = value; }
        }

        public T Data
        {
            get { return data; }
            set { this.data = value; }
        }
    }

Als nächstes implementieren wir die Operation der verknüpften Liste und erstellen eine verknüpfte Liste. In der erstellten verknüpften Liste definieren wir ein Objekt des Kopfknotens Sehr nützlicher Knoten. Sie können es im folgenden Code langsam erkennen

    public class MyLinkList<T>
    {
       public Node<T> Head { get; set; }

        //构造器  
        public MyLinkList()
        {
            Head = null;
        }
    }

1. Finden Sie die Länge der verknüpften Liste, Idee: Gehen Sie vom Anfangsknoten rückwärts bis zum letzten Knoten , der Code lautet wie folgt:

       public int Length()
        {
            var p = Head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }

2 Löschen Sie die verknüpfte Liste. Dies ist relativ einfach. Der Code lautet wie folgt 🎜>

3. Der gleiche Weg ist erforderlich, um festzustellen, ob die verknüpfte Liste leer ist. Verwenden Sie den Kopfknoten

        public void Clear()
        {
            Head = null;
        }

4. Fügen Sie a hinzu Um ein neues Element am Ende der verknüpften Liste hinzuzufügen, müssen Sie zunächst feststellen, ob die verknüpfte Liste leer ist. Wenn sie leer ist, müssen Sie dem Kopfknoten eine Punktzuweisung geben Der nächste Zeiger des letzten Knotens muss wie folgt geändert werden:

        public bool IsEmpty()
        {
            if (Head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

5. Fügen Sie eine Spezifikation vor der Position des i-ten Knotens in die einfach verknüpfte Liste ein Knoten, Sie müssen zuerst die Einfügeposition finden und dann die Richtung des angrenzenden Knotens ändern. Der Code lautet wie folgt:

       public void Append(T item)
        {

            if (Head == null)
            {
                Head = new Node<T>(item, null);
                return;
            }
            var p = new Node<T>();
            p = Head;
            while (p.Next != null)
            {
                p = p.Next;
            }
            p.Next = new Node<T>(item, null);
        }

6. Um zuerst den angegebenen Knoten zu löschen Suchen Sie den vorherigen zu löschenden Knoten und ändern Sie dann den nächsten Zeiger des Knotens. . . .

        public void Insert(T item, int i)
        {

            if (IsEmpty() || i < 1 || i > GetLength())
            {
                return;
            }
            //如果在第一个位置插入 则只需要将该节点的next 指向head即可
            if (i == 1)
            {
                var first = new Node<T>(item, null);
                first.Next = Head;
                Head = first;
                return;
            }

            var p = new Node<T>();
            p = Head;
            var left = new Node<T>();
            var right = new Node<T>();
            int j = 1;
            while (p.Next != null && j < i)
            {
                left = p;
                right = p.Next;
                ++j;
            }
            var q = new Node<T>(item, null);
            left.Next = q;
            q.Next = right;
        }

·7. Verknüpfte Listen enthalten auch Vorgänge wie Löschen, Erfassen und Suchen. Die Grundideen sind dieselben, daher werde ich sie nicht einzeln vorstellen verknüpfte Listen

1. Finden Sie die Anzahl der Knoten in der einfach verknüpften Liste

2. Kehren Sie die einfach verknüpfte Liste um

3. Suchen Sie den K-ten Knoten vom letzten in der einfach verknüpften Liste (k > ; 0)

4. Finden Sie den einzelnen mittleren Knoten der verknüpften Liste

5. Drucken Sie die einfach verknüpfte Liste vom Ende bis zum Kopf

6. Es ist bekannt, dass die beiden einfach verknüpften Listen pHead1 und pHead2 sind jeweils in der richtigen Reihenfolge, und das Zusammenführen zu einer verknüpften Liste bleibt weiterhin in der richtigen Reihenfolge
7. Bestimmen Sie, ob es einen Ring in einer einfach verknüpften Liste gibt
8. Bestimmen Sie, ob sich zwei einfach verknüpfte Listen überschneiden
9. Suchen Sie den ersten Knoten, an dem sich zwei einfach verknüpfte Listen schneiden
10. Es ist bekannt, dass es in einer einfach verknüpften Liste einen Ring gibt. Suchen Sie den Eintrag. Der erste Knoten im Ring
11. Gegeben sei ein einzelner verknüpfter Listenkopfzeiger pHead und ein Knotenzeiger pToBeDeleted, die O(1)-Zeitkomplexität besteht darin, den Knoten pToBeDeleted zu löschen



Okay, das war's fürs Erste. Sie können sie beantworten . Wenn Sie Fragen haben, kontaktieren Sie mich bitte

　

Das obige ist der detaillierte Inhalt vonWas ist eine verknüpfte Liste? Was ist der Unterschied zwischen verknüpfter Liste und Array?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!