Qu'est-ce qu'une liste chaînée ? Quelle est la différence entre une liste chaînée et un tableau ?

Compilation des connaissances connexes sur les listes chaînées

Qu'est-ce qu'une liste chaînée

Une liste chaînée est une structure de stockage non continue et non séquentielle sur une unité de stockage physique L'ordre logique. des éléments de données se fait via la liste chaînée. L'ordre des liens du pointeur est implémenté. Une liste chaînée se compose d'une série de nœuds (chaque élément de la liste chaînée est appelé un nœud) et les nœuds peuvent être générés dynamiquement au moment de l'exécution. Chaque nœud se compose de deux parties : l'une est le champ de données qui stocke les éléments de données et l'autre est le champ de pointeur qui stocke l'adresse du nœud suivant.

La différence entre les listes chaînées et les tableaux

Rappelez-vous le concept de tableaux. Le soi-disant tableau est une collection d'éléments du même type de données disposés dans un certain ordre. Selon le concept, nous pouvons savoir que les tableaux sont continus en mémoire et que les listes chaînées ne sont pas continues ; en raison de différentes méthodes de stockage, les tableaux allouent de la mémoire de manière statique et les listes chaînées allouent de la mémoire de manière dynamique. Les éléments du tableau sont dans la zone de pile et les éléments de la liste chaînée le sont. dans la zone du tas. Étant donné que les tableaux sont continus en mémoire, nous pouvons utiliser des indices pour localiser, la complexité temporelle est O(1), et la complexité temporelle de la localisation des éléments dans la liste chaînée est cependant O(n) ; continuité du tableau, la complexité temporelle de l'insertion ou de la suppression d'éléments du tableau est O(n) et la complexité temporelle de la liste chaînée est O(n) Complexité O(1). Pour résumer, la différence entre les tableaux et les listes chaînées est la suivante
1. Les tableaux allouent de la mémoire de manière statique et les listes chaînées allouent de la mémoire dynamiquement
2. Les tableaux sont continus en mémoire et les listes chaînées sont discontinues
3. Les éléments du tableau sont dans la zone de pile et les éléments de liste chaînée sont dans la zone de pile.
4. Le tableau est positionné à l'aide d'indices et la complexité temporelle est O(1). dans la liste chaînée est O(n);
5. La complexité temporelle de l'insertion ou de la suppression d'éléments du tableau est O( n), la complexité temporelle de la liste chaînée est O(1).

C# implémente les opérations de base des listes chaînées

En prenant comme exemple une liste chaînée, selon la définition d'une liste chaînée, nous définissons d'abord la structure de données des nœuds de la liste chaînée

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

Ensuite, nous allons implémenter le fonctionnement de la liste chaînée et construire une liste chaînée, nous définissons un objet du nœud principal. nœud très utile. Vous pouvez le réaliser lentement dans le code suivant

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

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

1. Trouver la longueur de la liste chaînée, idée : visiter en arrière du nœud de début jusqu'au dernier nœud. , le code est le suivant

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

2 . Effacez la liste chaînée C'est relativement simple, définissez simplement le nœud principal sur null. 🎜>

        public void Clear()
        {
            Head = null;
        }

3. La même manière est requise pour déterminer si la liste chaînée est vide. Utilisez le nœud principal

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

4. Ajoutez un. nouvel élément à la fin de la liste chaînée. Pour ajouter un nouvel élément, vous devez d'abord déterminer si la liste chaînée est vide. Si elle est vide, nous devons attribuer un point au nœud principal, si elle n'est pas vide, vous. il faut modifier le pointeur suivant du dernier nœud. Le code est le suivant

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

5. Insérez une spécification avant la position du i-ème nœud dans la liste à chaînage unique. Nœud, vous devez d'abord trouver la position d'insertion, puis modifier la direction du nœud adjacent. Le code est le suivant

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

6. Pour supprimer le nœud spécifié, commencez par supprimer le nœud spécifié. recherchez le nœud précédent à supprimer, puis modifiez le pointeur suivant du nœud. Le code est omis. . . .

·7. Les listes chaînées comportent également des opérations telles que la suppression, l'acquisition et la recherche. Les idées de base sont les mêmes, je ne les présenterai donc pas un par un

Sujets classiques liés à. listes chaînées

1. Trouvez le nombre de nœuds dans la liste chaînée

2. Inversez la liste chaînée

3. Trouvez le Kème nœud du dernier dans la liste chaînée (k > ; 0)
4. Trouvez le nœud unique du milieu de la liste chaînée
5. Imprimez la liste chaînée unique de bout en tête
6. On sait que les deux listes chaînées simples pHead1 et pHead2 sont chacun dans l'ordre, et les fusionner en une seule liste chaînée sera toujours dans l'ordre
7. Déterminez s'il y a un anneau dans une liste chaînée
8. Déterminez si deux listes chaînées se croisent
9. Trouvez le premier nœud où deux listes chaînées se croisent
10. On sait qu'il y a un anneau dans une liste chaînée, trouvez l'entrée Le premier nœud de l'anneau
11. Étant donné un seul pointeur de tête de liste chaînée pHead et un pointeur de nœud pToBeDeleted, la complexité temporelle O(1) est de supprimer le nœud pToBeDeleted

D'accord C'est tout pour l'instant. Les questions proviennent de l'offre Jianzhi. Vous pouvez y répondre. . Si vous avez des questions, n'hésitez pas à me contacter

　

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!