Java 데이터 구조에서 연결리스트의 개념과 구조는 무엇입니까?

1. 연결 리스트의 개념

개념: 연결 리스트는 비연속적이고 비순차적인 물리적 저장 구조입니다. 연결 리스트의 포인터 링크 순서를 통해 데이터 요소의 논리적 순서가 구현됩니다. 1. 연결리스트는 일련의 노드로 구성됩니다(연결리스트의 각 요소를 노드라고 합니다).

2. 노드는 런타임에 동적으로(malloc) 생성될 수 있습니다.

3. 각 노드는 두 부분으로 구성됩니다. 하나는 데이터 요소를 저장하는 데이터 필드이고 다른 하나는 다음 노드의 주소를 저장하는 포인터 필드입니다(자세한 내용은 1.2 노드 섹션 참조).

4. 선형 목록 순서 구조에 비해 연결 목록 작업이 복잡합니다. 그러나 순서대로 저장할 필요가 없기 때문에 연결 목록은 삽입 시 O(1) 복잡도를 얻을 수 있으며 이는 순차 목록보다 훨씬 빠릅니다. 그러나 노드를 검색하거나 특정 번호의 노드에 액세스하려면 필요합니다. O(n) 시간이고 시퀀스 목록에는 O(1)

2만 필요합니다. 노드

연결 목록은 노드로 구성되며 각 노드는 구조체 형태입니다. 구조의 첫 번째 변수는 필요에 따라 제공됩니다. 마지막 변수는 다음 노드의 첫 번째 주소를 저장하는 데 사용되는 이 구조 유형의 포인터입니다‘

연결된 목록 노드는 두 개의 필드로 나뉩니다

데이터 필드: 다양한 실제 데이터를 저장합니다.

포인터 필드: 다음 노드의 주소를 저장합니다.

(사진은 센티널 헤더 노드가 있는 연결 목록을 보여줍니다.)

3. 연결 목록의 사용 시나리오

선형 테이블은 자주 삽입해야 합니다. 또는 데이터 요소 삭제

이 경우 체인 저장 구조가 적합합니다.

연결된 목록의 경우 데이터를 삽입하거나 삭제하려면 노드를 만들고, 데이터를 입력하고, 노드를 연결 목록의 특정 위치에 연결하기 위한 포인터만 수정하면 되지만, 순차 목록의 경우 데이터를 삽입하려면 이동이 필요할 수 있습니다. 다른 데이터는 복잡성이 높습니다.

4. 연결 목록 분류 및 일반적으로 사용되는 구조

총 8가지 유형의 연결 목록 중에서 선택할 수 있지만 실제로 가장 일반적으로 사용되는 유형은 헤드리스 단방향 비순환입니다.

연결 목록 및

led 양방향 루프 연결 목록. 1. 헤드리스 단방향 비순환 연결 목록: 일반적으로 "단일 연결 목록"으로 알려져 있습니다. 구조가 단순하여 일반적으로 데이터만 단독으로 저장하는 데에는 사용되지 않습니다. 실제로 이는 다른 데이터 구조(예: 해시 버킷, 그래프의 인접 목록, 스택의 체인 구조 등)의 하위 구조에 가깝습니다.

2. 방향이 있는 양방향 순환 연결 목록: 일반적으로 사용되는 가장 복잡한 구조입니다. 데이터를 별도로 저장합니다. 실제로 사용되는 연결 목록의 대부분은 양방향 순환 연결 목록으로 향합니다. 구조가 가장 복잡하지만 이 구조는 많은 장점을 제공합니다.

5. 순차 목록과 비교

연결 목록:

연결 목록은 노드를 통해 개별 데이터를 테이블에 연결하고, 노드 삽입 및 삭제를 통해 데이터에 액세스합니다.

시퀀스 테이블:

시퀀스 테이블은 연속 메모리를 열어(직접 배열이나 malloc을 사용한 다음 realloc 확장을 사용하여) 데이터를 저장합니다.

하지만 realloc

확장은 in-situ 확장과 off-site 확장으로 나누어지므로 전자는 비용이 덜 드는 반면, 후자는 데이터 복사뿐만 아니라 확장 시 기존 공간도 해제해야 합니다. 또한 확장 시 일반적으로 원래 용량의 2배로 확장되며 너무 많이 확장하면 공간 낭비가 발생하기 쉽습니다. 노드는 표준 c 유형이거나 사용자 정의 구조 유형일 수 있습니다.

비교 개체

순차 목록링크된 목록연속불연속포인터만 수정하세요푸시할 때 새 노드를 직접 malloc합니다. 데이터 삽입 및 삭제가 잦음

		저장 공간
	삽입 또는 데이터 삭제	가능 데이터 이동의 복잡성은 O (n)
	push	동적 시퀀스 테이블: 공간이 부족하여 확장해야 합니다.
	애플리케이션	자주 액세스 필요

위 내용은 Java 데이터 구조에서 연결리스트의 개념과 구조는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!