연결리스트란 어떤 데이터 구조인가요?

연결된 목록은 물리적 저장 장치의 비연속적이며 비순차적인 저장 구조입니다. 간단히 말해서 연결 저장소에서 생성된 테이블의 포인터 링크 순서를 통해 데이터 요소의 논리적 순서가 실현됩니다. 선형 리스트의 구조를 '연결 리스트'라고 합니다. 연결된 목록의 각 데이터 요소는 두 부분으로 구성됩니다. 1. "데이터 필드"라고 하는 정보 자체 2. "포인터 필드"라고 하는 직접 후속 항목에 대한 포인터. 정보의 이 두 부분은 "노드"라고 불리는 데이터 요소의 저장 구조를 형성합니다. n개의 노드는 포인터 필드를 통해 서로 연결되어 연결 목록을 형성합니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

데이터 구조는 컴퓨터가 데이터를 저장하고 구성하는 방식입니다. 데이터 구조는 서로 하나 이상의 특정 관계를 갖는 데이터 요소의 모음을 나타냅니다. 신중하게 선택한 데이터 구조는 종종 운영 또는 저장 효율성을 높일 수 있습니다. 데이터 구조는 효율적인 검색 알고리즘 및 인덱싱 기술과 관련이 있는 경우가 많습니다.

데이터 구조의 链表

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

논리적 구조에 연달아 있는 데이터는 실제로 저장했을 때 시퀀스 테이블처럼 나란히 있지 않습니다. 반대로, 데이터는 메모리의 다양한 위치에 무작위로 분산됩니다. 이러한 저장 구조를 선형 목록의 연결 저장소라고 합니다.

분산형 저장으로 인해 데이터 요소 간의 논리적 관계를 반영하기 위해 각 데이터 요소에는 저장하는 동안 직접 후속 요소를 가리키는 포인터가 장착되어야 합니다. 즉, 각 데이터 요소는 다음 데이터를 가리킵니다. 요소(마지막 요소는 NULL(비어 있음)을 가리킴)

위 그림과 같이 각 데이터 요소를 포인터로 다음 데이터 요소에 연결하면 체인이 형성되고 이 체인의 헤드가 첫 번째 데이터 요소에 위치하는 방식입니다. 체인 스토리지입니다.

선형 리스트의 연결 저장 구조로 생성된 테이블을 "연결 리스트"라고 합니다.

연결된 목록의 데이터 요소 구성

각 요소 자체는 두 부분으로 구성됩니다.

• 정보 자체를 "데이터 필드"라고 합니다.

• 직접 후속 항목에 대한 포인터입니다. "포인터 필드"라고 합니다.

정보의 이 두 부분은 "노드"라고 불리는 데이터 요소의 저장 구조를 구성합니다. n개의 노드는 포인터 필드를 통해 서로 연결되어 연결 리스트를 형성합니다.

헤드 노드, 헤드 포인터 및 첫 번째 노드

헤드 노드: 때때로 연결 목록의 첫 번째 노드 앞에 추가 노드가 추가되고 해당 노드의 데이터 필드는 일반적으로 저장되지 않습니다. 어떤 경우에는 연결된 목록의 길이와 같은 정보도 저장할 수 있습니다. 이 노드를 헤드 노드라고 합니다.

헤드 노드의 포인터 필드가 NULL이면 연결 리스트가 빈 리스트임을 나타냅니다. 연결된 목록에는 헤드 노드가 필요하지 않습니다. 특정 문제를 처리할 때 연결된 목록에 헤드 노드를 추가하면 문제가 더 간단해집니다.

첫 번째 노드: 연결 리스트의 첫 번째 요소가 위치한 노드입니다. 헤드 노드 다음의 첫 번째 노드입니다.

헤드 포인터: 항상 연결된 목록의 첫 번째 노드 위치를 가리킵니다(연결된 목록에 헤드 노드가 있는 경우 헤드 포인터는 헤드 노드를 가리키고, 그렇지 않으면 헤드 포인터는 첫 번째 노드를 가리킵니다).

헤드 노드와 헤드 포인터의 차이점: 헤드 포인터는 헤드 노드 또는 연결 목록의 첫 번째 노드를 가리키는 포인터입니다. 헤드 노드는 데이터 필드와 포인터 도메인을 포함하는 실제 노드입니다. 프로그램에서 이 두 가지를 직접적으로 표현한 것은 헤드 포인터만 선언하고 저장 공간을 할당하지 않고, 헤드 노드를 선언하고 노드의 실제 물리적 메모리를 할당하는 것입니다.

연결된 목록 구조를 사용하면 데이터 크기를 미리 알아야 하는 배열 연결 목록의 단점을 극복할 수 있습니다. 연결 목록 구조는 컴퓨터 메모리 공간을 최대한 활용하고 유연한 동적 메모리를 구현할 수 있습니다. 관리. 그러나 연결리스트는 배열을 무작위로 읽는 장점을 상실하며, 동시에 노드의 포인터 필드의 증가로 인해 연결리스트의 공간 오버헤드가 상대적으로 크다. 연결된 목록의 가장 확실한 이점은 기존 배열이 관련 항목을 배열하는 방식이 이러한 데이터 항목이 메모리나 디스크에 배열되는 순서와 다를 수 있으며, 데이터에 액세스하려면 종종 다른 배열 사이를 전환해야 한다는 것입니다.

특징

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

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

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

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

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

연결된 목록에서 노드 삽입 및 제거

연결된 목록은 테이블의 어느 위치에서든 노드를 삽입하고 제거할 수 있지만 임의 액세스는 허용되지 않습니다.

1. 연결리스트에 노드 삽입

• 링크드 리스트에 헤드 노드를 삽입합니다. 삽입 위치에 따라 3가지 유형으로 구분됩니다.

• 링크드 리스트의 헤드에 삽입합니다. 즉, 헤드 노드와 노드 중간의 첫 번째 요소

• 가 연결 목록의 중간에 삽입됩니다.

삽입 위치는 다르지만 모두 동일한 삽입 기술을 사용합니다. 위 그림과 같이 두 단계로 나뉩니다.

새 노드의 다음 포인터를 삽입 위치 뒤의 노드에 가리킵니다.

• 삽입 위치 앞의 노드의 다음 포인터를 가리킵니다. 삽입 노드

• 팁: 삽입 작업을 할 때는 먼저 삽입 위치에서 이전 노드를 찾아야 합니다. 즉, 그림 4에서 노드 1을 찾으세요. 해당 노드 2는 다음 포인터로 나타낼 수 있습니다. 이런 식으로 먼저 1단계로 진행한 후 2단계로 진행합니다. 구현 과정에서 다른 보조 포인터를 추가할 필요가 없습니다.

2. 연결 목록에서 노드 삭제

연결 목록에서 노드를 삭제해야 하는 경우 다음 두 단계를 수행해야 합니다.

연결 목록에서 노드를 선택합니다.

• 노드 노드가 차지하는 메모리 공간을 재활용하려면 클릭하세요.

• 더 많은 관련 지식은

  FAQ
칼럼을 방문해주세요!

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