Related knowledge of linked lists

What is a linked list

A linked list is a non-continuous, non-sequential storage structure on a physical storage unit. The logical order of data elements is through the linked list. Pointer link order is implemented. A linked list consists of a series of nodes (each element in the linked list is called a node), and nodes can be dynamically generated at runtime. Each node consists of two parts: one is the data field that stores data elements, and the other is the pointer field that stores the address of the next node.

The difference between linked lists and arrays

Recall the concept of arrays. The so-called array is a collection of elements of the same data type arranged in a certain order. According to the concept, we can know that arrays are continuous in memory and linked lists are not continuous; due to different storage methods, arrays statically allocate memory and linked lists dynamically allocate memory. Array elements are in the stack area and linked list elements are in the heap area. Since arrays are continuous in memory, We can use subscripts to locate, the time complexity is O(1), and the time complexity of locating elements in the linked list is O(n); however, due to the continuity of the array, the time complexity of inserting or deleting elements from the array is O(n), and the time complexity of the linked list is O(n). Complexity O(1). To summarize, the difference between arrays and linked lists is as follows
1. Arrays allocate memory statically, linked lists dynamically allocate memory
2. Arrays are continuous in memory, linked lists are discontinuous
3. Array elements are in the stack area, and linked list elements are in the stack area In the heap area
　4. The array is positioned using subscripts, and the time complexity is O(1). The time complexity of locating elements in the linked list is O(n);
　5. The time complexity of inserting or deleting elements from the array is O( n), the time complexity of the linked list is O(1).

C# Implement the basic operations of a linked list

Taking a singly linked list as an example, according to the definition of a linked list, we first define the data structure of the linked list node

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

Copy after login

Next, let's implement the operation of the linked list and construct a linked list. In the constructed linked list, we define an object of the head node. The head node is a very useful node. You can slowly realize it in the subsequent code

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

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

Copy after login

1. Find the length of the linked list, idea: visit backward from the beginning node until the last node, the code is as follows

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

Copy after login

2. Clear the linked list, this is It is relatively simple. Just set the head node to null. The code is as follows

        public void Clear()
        {
            Head = null;
        }

Copy after login

3. In the same way, the head node is also used to determine whether the linked list is empty

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

Copy after login

4. Add a new element at the end of the linked list. To add a new element, you need to first determine whether the linked list is empty. If it is empty, we need to assign a value to the head node. If it is not empty, you need to modify the last node. The next point of a node points to the following code. Just point to the adjacent node, the code is as follows

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

Copy after login

6. To delete the specified node, first find the previous node to be deleted, and then modify the next point of the node. Code slightly. . . .

· 7. Linked lists also have operations such as deletion, acquisition, and search. The basic ideas are the same, so I will not introduce them one by one.

Classic topics related to linked lists

1. Find the number of nodes in the singly linked list

　2. Reverse the singly linked list

　3. Find the Kth node from the last in the singly linked list (k > 0)

　4. Find the single linked list The intermediate node of the linked list

　5. Print the singly linked list from end to head
　6. It is known that the two singly linked lists pHead1 and pHead2 are each in order, and merging them into one linked list will still be in order
　7. Determine a Whether there is a cycle in a singly linked list
8. Determine whether two singly linked lists intersect
9. Find the first node where two singly linked lists intersect
10. It is known that there is a cycle in a singly linked list, find the entry The first node in the ring
11. Given a single linked list head pointer pHead and a node pointer pToBeDeleted, O(1) time complexity is required to delete the node pToBeDeleted

Okay That’s it for now. The questions are from the Jianzhi offer. You can answer them. If you have any questions, please contact me

The above is the detailed content of What is a linked list? What is the difference between linked list and array?. For more information, please follow other related articles on the PHP Chinese website!