링크드 리스트 관련 지식 정리

링크드 리스트란 무엇인가

링크드 리스트는 물리적 저장 단위의 비연속적이고 비순차적인 저장 구조입니다. 데이터 요소의 논리적 순서는 링크 순서를 통해 구현됩니다. 연결리스트의 포인터. 연결된 목록은 일련의 노드(연결된 목록의 각 요소를 노드라고 함)로 구성되며 노드는 런타임에 동적으로 생성될 수 있습니다. 각 노드는 두 부분으로 구성됩니다. 하나는 데이터 요소를 저장하는 데이터 필드이고 다른 하나는 다음 노드의 주소를 저장하는 포인터 필드입니다.

연결된 목록과 배열의 차이점

　 배열의 개념을 떠올려보세요. 소위 배열은 동일한 데이터 유형의 요소를 특정 순서로 배열한 것입니다. 개념에 따르면 배열은 메모리에서 연속적이고 연결 목록은 연속적이지 않다는 것을 알 수 있습니다. 배열은 메모리를 정적으로 할당하고 연결 목록은 동적으로 메모리를 할당하며 배열 요소는 스택 영역에 있습니다. 힙 영역에서 배열은 메모리에서 연속적이므로 첨자를 사용하여 찾을 수 있으며 시간 복잡도는 O(1)이고 연결된 목록에서 요소를 찾는 시간 복잡도는 O(n)입니다. 배열의 연속성에서 요소를 삽입하거나 삭제하는 시간 복잡도는 O(n)이고 연결 목록의 시간 복잡도는 O(1)입니다. 배열과 연결리스트의 차이점을 정리하면
　1. 배열은 메모리를 정적으로 할당하고, 연결리스트는 동적으로 메모리를 할당합니다
　2. 배열은 메모리 내에서 연속적이지만 연결리스트는 불연속적입니다
　3. 배열 요소는 스택에 있습니다. 힙 영역에 있고 연결 목록 요소는 힙 영역에 있습니다
　4. 배열은 첨자를 사용하여 배치되며 시간 복잡도는 O(1)이고 연결 목록의 시간 복잡도는 O(n) 입니다. 배열에 요소를 삽입하거나 삭제하는 것은 O(n)이고 연결리스트의 요소는 O(1)입니다.

C#은 연결 목록의 기본 작업을 구현합니다.

단일 연결 목록을 예로 들어 연결 목록의 정의에 따라 먼저 연결 목록 노드의 데이터 구조를 정의합니다.

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

로그인 후 복사

다음으로 구현합니다. 연결된 목록의 작업을 수행하고 연결된 목록을 구성합니다. 헤드 노드의 객체를 정의합니다. 헤드 노드는 후속 코드에서 천천히 실현할 수 있습니다. .연결된 목록의 길이를 찾으십시오. 아이디어는 마지막 노드까지 헤드 노드에 액세스하는 것입니다. 코드는 다음과 같습니다.

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

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

로그인 후 복사

2. 연결 목록을 지우면 비교적 간단합니다. 헤드 노드만 설정하면 됩니다. null로 설정하려면 코드는 다음과 같습니다

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

로그인 후 복사

3. 같은 방식으로 연결 목록이 비어 있는지 확인합니다. 또한 헤드 노드를 사용합니다

        public void Clear()
        {
            Head = null;
        }

로그인 후 복사

4. 연결 목록 끝에 새 요소를 추가합니다. 새 요소를 추가하려면 먼저 연결된 목록이 비어 있는지 확인해야 하며, 비어 있으면 헤드 노드에 값을 할당해야 하며, 비어 있지 않으면 마지막 항목의 다음 지점을 수정해야 합니다.

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

로그인 후 복사

5. 단일 연결 리스트의 i번째 노드 앞에 지정된 노드를 삽입한 후, 먼저 삽입 위치를 찾은 후 인접한 노드의 지점을 수정해야 합니다. 즉, 코드는 다음과 같습니다

       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. 지정된 노드를 삭제하려면 먼저 삭제할 이전 노드를 찾은 후 노드의 다음 지점을 수정합니다. . . .

·　7. 연결리스트에도 삭제, 획득, 검색 등의 연산이 있는데 기본적인 개념은 동일하므로 하나씩 소개하지 않겠습니다

연결리스트에 관련된 대표적인 질문

　1. 갯수를 찾아보세요. 단일 연결 리스트의 노드

2. 단일 연결 리스트를 뒤집는다

　3. 단일 연결 리스트의 마지막 노드에서 K번째 노드를 찾는다(k>0)

　4. 단일 연결 리스트의 중간 노드를 찾는다

5. 단일 연결 리스트를 끝부터 처음까지 인쇄합니다

　6. 이미 우리는 두 개의 단일 연결 리스트 pHead1과 pHead2가 각각 순서대로 있다는 것을 알고 있습니다. 이들을 하나의 연결 리스트로 병합하면 여전히 순서가 유지됩니다
　7. 단일 연결 리스트의 순환
　8. 두 개의 단일 연결 리스트가 교차하는지 확인
　9. 두 개의 단일 연결 리스트 찾기 교차하는 첫 번째 노드
　10. 단일 연결 리스트에는 링이 있는 것으로 알려져 있으며, 첫 번째 노드를 찾습니다. 링에 들어가는 노드
　11. 단일 연결 리스트 헤드 포인터 pHead와 노드 포인터 pToBeDeleted가 주어지면 시간 복잡도는 O(1) 정도 삭제된 노드 pToBeDeleted

자, 질문은 여기서 멈추겠습니다. 질문이 있으시면 연락주세요

위 내용은 연결리스트란 무엇인가요? 연결리스트와 배열의 차이점은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!