연결리스트란 무엇인가

연결된 목록은 물리적 저장 단위의 비연속적이고 비순차적인 저장 구조입니다. 데이터 요소의 논리적 순서는 연결 목록의 포인터 링크 순서를 통해 구현됩니다. 연결된 목록은 일련의 노드(연결된 목록의 각 요소를 노드라고 함)로 구성되며 노드는 런타임에 동적으로 생성될 수 있습니다. 각 노드는 두 부분으로 구성됩니다. 하나는 데이터 요소를 저장하는 데이터 필드이고 다른 하나는 다음 노드의 주소를 저장하는 포인터 필드입니다. 선형 테이블 시퀀스 구조에 비해 작업이 복잡합니다. 연결리스트는 순서대로 저장할 필요가 없기 때문에 삽입 시 O(1) 복잡도를 달성할 수 있는데, 이는 다른 선형 목록, 순차 목록보다 훨씬 빠르지만 노드를 찾거나 특정 번호가 매겨진 노드에 접근하려면 O(n)이 필요합니다. ) 시간이고 선형 테이블과 순차 테이블의 해당 시간 복잡도는 각각 O(logn) 및 O(1)입니다.

연결된 목록 구조를 사용하면 데이터 크기를 미리 알아야 하는 배열 연결 목록의 단점을 극복할 수 있습니다. 연결 목록 구조는 컴퓨터 메모리 공간을 최대한 활용하고 유연한 동적 메모리 관리를 달성할 수 있습니다. 그러나 연결리스트는 배열을 무작위로 읽는 장점을 잃는 동시에 노드의 포인터 필드 증가로 인해 상대적으로 큰 공간 오버헤드를 갖게 됩니다. 연결된 목록의 가장 분명한 이점은 일반 배열이 관련 항목을 정렬하는 방식이 이러한 데이터 항목이 메모리나 디스크에 정렬되는 순서와 다를 수 있으며 데이터에 액세스하려면 종종 다른 배열 간에 전환해야 한다는 것입니다. 연결 목록을 사용하면 목록의 어느 위치에서나 노드를 삽입하고 제거할 수 있지만 임의 액세스는 허용되지 않습니다. 연결 목록에는 단방향 연결 목록, 이중 연결 목록, 순환 연결 목록 등 다양한 유형이 있습니다. 연결된 목록은 다양한 프로그래밍 언어로 구현될 수 있습니다. Lisp 및 Scheme과 같은 언어의 내장 데이터 유형에는 연결된 목록의 액세스 및 작동이 포함됩니다. C, C++ 및 Java와 같은 프로그래밍 또는 객체 지향 언어는 연결 목록을 생성하기 위해 변경 가능한 도구를 사용합니다.

Features

선형 테이블의 연결된 저장소 표현의 특징은 임의의 저장 단위 집합을 사용하여 선형 테이블의 데이터 요소를 저장하는 것입니다(이 저장 단위 집합은 연속적이거나 불연속적일 수 있음). 따라서 각 데이터 요소와 그 직접적인 후속 데이터 요소 사이의 논리적 관계를 표현하기 위해서는 해당 데이터 요소에 대해 자신의 정보를 저장하는 것 외에도 직접 후속하는 데이터 요소를 나타내는 정보(즉, 저장 공간)도 저장해야 한다. 직계 후계자 위치). 이 두 가지 정보 조각은 선형 테이블의 데이터 요소를 나타내는 "노드"(개요 옆 그림 참조)를 형성합니다. 선형 테이블의 연결된 스토리지 표현의 한 가지 단점은 숫자를 찾으려면 처음부터 시작해야 하며 이는 매우 번거롭다는 것입니다.

상황에 따라 연결 리스트의 다른 확장을 직접 디자인할 수도 있습니다. 그러나 연결리스트의 점과 변은 기본적으로 일대일 대응이기 때문에 일반적으로 변에는 데이터가 추가되지 않습니다. (첫 번째 또는 마지막 노드를 제외하고 특별한 상황은 발생하지 않습니다.) 그러나 특별한 경우는 연결된 목록이 연결된 목록의 섹션에서 앞 포인터와 뒤 포인터의 반전을 지원하는 경우 가장자리에 반전 표시를 추가하는 것이 더 편리할 수 있다는 것입니다.

비선형 연결 목록의 경우 트리, 그래프 등 다른 관련 데이터 구조를 참조할 수 있습니다. 다중 선형 연결 목록을 기반으로 하는 데이터 구조도 있습니다. 즉, 삽입, 삭제, 검색과 같은 기본 작업의 속도는 균형 이진 트리와 마찬가지로 O(nlogn)에 도달할 수 있습니다.

데이터 요소 정보를 저장하는 도메인을 데이터 도메인(도메인 이름을 데이터로 함)이라고 하며, 직접적인 후속 저장 위치를 ​​저장하는 도메인을 포인터 도메인(도메인 이름을 다음으로 함)이라고 합니다. 포인터 필드에 저장된 정보를 포인터 또는 체인이라고도 합니다.

각각 ,...을 나타내는 N개의 노드로 구성된 연결 목록을 선형 목록의 연결 저장소 표현이라고 합니다. 이 유형의 연결 목록의 각 노드에는 하나의 포인터 필드만 포함되므로 단일 연결 리스트(Single Linked List) 또는 선형 연결 리스트(Linear Linked List)라고도 합니다.

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