링크 리스트

링크 리스트는 2개의 필드(정수값과 다음 노드에 대한 링크)를 포함하는 노드의 시퀀스입니다.마지막 노드는 목록의 끝을 나타내기 위해 사용되는 터미네이터에 링크됩니다.

컴퓨터 과학에서 링크드 리스트는 메모리 내의 물리적인 위치에 의해 순서가 부여되지 않는 데이터 요소의 선형 집합입니다.대신 각 요소는 다음 요소를 가리킵니다.이는 함께 시퀀스를 나타내는 노드의 집합으로 구성된 데이터 구조입니다.가장 기본적인 형태로 각 노드에는 데이터 및 시퀀스 내의 다음 노드에 대한 참조(즉, 링크)가 포함됩니다.이 구조를 사용하면 반복 중에 시퀀스의 모든 위치에서 요소를 효율적으로 삽입 또는 제거할 수 있습니다.더 복잡한 변형에서는 링크가 추가되어 임의의 위치에서 노드를 보다 효율적으로 삽입 또는 제거할 수 있습니다.링크 리스트의 단점은 액세스 시간이 선형적이라는 것입니다(파이프라인이 어렵습니다).랜덤 액세스 등 고속 액세스는 불가능합니다.어레이는 링크된 목록에 비해 캐시 인접성이 우수합니다.

링크 리스트는 가장 단순하고 일반적인 데이터 구조 중 하나입니다.이들은 목록, 스택, 큐, 연관 배열, S-표현식 등 몇 가지 일반적인 추상 데이터 유형을 구현하는 데 사용할 수 있지만 링크된 목록을 기반으로 사용하지 않고 이러한 데이터 구조를 직접 구현하는 것은 드문 일이 아닙니다.

기존 어레이에 비해 링크 리스트의 주요 장점은 데이터 항목을 메모리나 디스크에 연속적으로 저장할 필요가 없기 때문에 전체 구조를 재할당하거나 재구성하지 않고도 목록 요소를 쉽게 삽입하거나 제거할 수 있다는 것입니다.또한 런타임에 어레이를 재구성하는 것은 비용이 많이 들기 때문입니다.링크된 목록을 사용하면 목록 내의 임의의 포인트에서 노드를 삽입 및 삭제할 수 있습니다.또한 링크의 추가 또는 삭제 전 링크를 리스트트래버설 중에 메모리에 보관 유지함으로써 일정 횟수의 조작을 실행할 수 있습니다.

한편, 단순한 링크 리스트 자체로는 데이터 또는 어떤 형태의 효율적인 인덱스에 대한 랜덤 액세스를 허용하지 않기 때문에 목록의 마지막 노드 취득, 특정 데이텀을 포함하는 노드 검출, 새 노드 삽입 장소 지정 등 많은 기본 조작이 대부분의 경우 또는 모든 데이터를 반복해야 할 수 있습니다.요소를 나열합니다.

역사

링크 리스트는 앨런 뉴웰, 클리프 쇼, 허버트 A에 의해 1955-1956년에 개발되었다. RAND Corporation의 Simon은 정보처리 언어의 주요 데이터 구조입니다.IPL은 논리 이론 기계, 일반 문제 해결사, 컴퓨터 체스 프로그램을 포함한 몇몇 초기 인공지능 프로그램을 개발하기 위해 저자들에 의해 사용되었다.1956년 IRE Transactions on Information Theory(정보이론에 관한 거래)에, 1957년 및 1958년 Western Joint Computer Conference(서양공동컴퓨터회의)의 Proceedings(Proceedings)와 1959년 Information Processing(제1회 유네스코 국제정보처리회의 Processing)의 Proceedings(Proceedings)를 포함한 1957년부터 1959년까지의 몇 개의 회의의 보고가 있었다.리스트 노드를 나타내는 블록과 연속되는 리스트노드를 가리키는 화살표로 구성된 고전적인 다이어그램은 Newell과 Proc의 Shaw의 "Programming the Logic Theory Machine"에 나와 있습니다.WJCC, 1957년 2월뉴웰과 사이먼은 "인공지능, 인간 인지 심리학, 목록 처리에 기본적인 공헌을 한" 공로로 1975년 ACM 튜링 상을 받았다.자연어 처리를 위한 기계번역 문제로 매사추세츠공과대학(MIT)의 Victor Yngve는 언어학 분야의 컴퓨터 연구를 위해 COMIT 프로그래밍 언어의 데이터 구조로서 링크 리스트를 사용했습니다.기계번역을 위한 프로그래밍 언어라는 제목의 이 언어에 대한 보고서는 1958년 ^{[citation needed]}기계번역에 실렸다.

링크 리스트의 또 다른 초기 출현은 1953년 1월에 체인 해시 테이블에서 링크 리스트의 사용을 제안하는 IBM 내부 메모를 작성한 Hans Peter Luhn에 의한 것입니다.^[1]

리스트 프로세서의 약자인 LISP는 존 매카시가 MIT에 있을 때 1958년에 창설되었으며, 1960년에 ACM의 Communications of Symbolic Expressions and They Computation by Machine, Part I이라는 제목의 논문에서 그 설계를 발표했습니다.LISP의 주요 데이터 구조 중 하나는 링크드 리스트입니다.

1960년대 초에는 이러한 구조를 주요 데이터 표현으로 사용하는 링크드 리스트와 언어의 효용성이 잘 확립되었다.MIT 링컨 연구소의 버트 그린은 1961년 3월 IRE Transactions on Human Factors in Electronics에서 링크 목록 접근법의 장점을 요약한 "기호 조작을 위한 컴퓨터 언어"라는 제목의 리뷰 기사를 발표했다.1964년 4월 ACM의 Communications of the ACM에 Bobrow와 Raphael의 리뷰 기사 "A Comparison of list-processing computer languages"가 실렸다.

Technical Systems Consultants가 개발한 여러 운영체제(원래는 West Lafayette Indiana, 나중에는 North Carolina Chapel Hill)는 단일 링크 목록을 파일 구조로 사용했습니다.디렉토리 엔트리는 파일의 첫 번째 섹터를 가리키며, 파일의 후속 부분은 포인터를 통과함으로써 배치됩니다.이 기술을 사용하는 시스템에는 Flex(Motorola 6800 CPU용), mini-Flex(동일한 CPU용), Flex9(Motorola 6809 CPU용)가 있습니다.TSC가 캘리포니아의 Smoke Signal Broadcasting을 위해 개발하고 시판한 변종은 동일한 방식으로 이중 링크 목록을 사용했다.

IBM이 System 360/370 시스템용으로 개발한 TSS/360 운영 체제는 파일 시스템 카탈로그에 이중 링크 목록을 사용했습니다.디렉토리 구조는 UNIX와 비슷하며, 디렉토리는 파일 및 기타 디렉토리를 포함할 수 있으며, 깊이가 제한되지 않습니다.

기본 개념과 용어

링크된 목록의 각 레코드는 종종 '요소' 또는 '노드'라고 불립니다.

다음 노드의 주소를 포함하는 각 노드의 필드를 보통 '다음 링크' 또는 '다음 포인터'라고 합니다.나머지 필드는 'data', 'information', 'value', 'cargo' 또는 'payload' 필드로 알려져 있습니다.

목록의 선두가 첫 번째 노드입니다.목록의 '꼬리'는 선두 뒤의 나머지 목록 또는 목록의 마지막 노드를 참조할 수 있습니다.Lisp 및 일부 파생 언어에서 다음 노드는 목록의 'cdr'(cand-er로 발음됨)으로 불리며, 헤드 노드의 payload는 'car'로 불리기도 합니다.

단일 링크 리스트

단일 링크 목록에는 데이터 필드와 노드 행의 다음 노드를 가리키는 '다음' 필드가 있는 노드가 포함됩니다.단일 링크 목록에 대해 수행할 수 있는 작업에는 삽입, 삭제 및 통과가 포함됩니다.

노드에 두 개의 필드(정수값과 다음 노드에 대한 링크)가 포함된 단일 링크 리스트

다음 코드는 단일 링크 목록의 끝에 데이터 "값"을 가진 새 노드를 추가하는 방법을 보여 줍니다.

노드 추가 노드(노드 머리, 인트 가치) {     노드 임시직, p; // 2노드의 온도와 p를 선언합니다.     임시직 = create Node(); // createNode가 데이터 = 0인 새 노드를 생성하고 다음으로 NULL을 가리킨다고 가정합니다.     임시직->데이터. = 가치; // 노드의 데이터 부분에 요소 값 추가     한다면 (머리 == 특수한 순서) {         머리 = 임시직;     // 링크된 목록이 비어 있는 경우     }     또 다른 {         p = 머리; // 헤드를 p에 할당         하는 동안에 (p->다음 분. != 특수한 순서) {             p = p->다음 분.; // p가 마지막 노드가 될 때까지 목록을 이동합니다.마지막 노드는 항상 NULL을 가리킵니다.         }         p->다음 분. = 임시직; // 이전 마지막 노드를 생성된 새 노드를 가리킵니다.     }     돌아가다 머리; }

이중 링크 리스트

'더블 링크 리스트'에서 각 노드는 다음 노드 링크 외에 시퀀스 내의 '이전' 노드를 가리키는 제2 링크 필드를 포함한다.두 링크를 'forward(s)'와 'backwards' 또는 'next'와 'prev'('prev'('이전')라고 할 수 있습니다.

노드에 3개의 필드(정수값, 다음 노드로의 링크 전송 및 이전 노드로의 링크)가 포함된 이중 링크 리스트

XOR 링크라고 불리는 기술을 사용하면 각 노드에서 단일 링크 필드를 사용하여 이중 링크 목록을 구현할 수 있습니다.단, 이 기술에는 주소에 대한 비트 조작이 필요하기 때문에 일부 고급 언어에서는 사용할 수 없는 경우가 있습니다.

대부분의 최신 운영 체제에서는 이중 링크 목록을 사용하여 활성 프로세스, 스레드 및 기타 동적 ^[2]개체에 대한 참조를 유지합니다.루트킷이 검출을 회피하기 위한 일반적인 전략은 ^[3]이들 목록에서 스스로 링크를 해제하는 것입니다.

다중 링크 리스트

'멀티 링크 리스트'에서 각 노드는 2개 이상의 링크 필드를 포함하며, 각 필드는 동일한 세트의 다른 순서(예를 들어 이름별, 부서별, 생년월일별 등)로 동일한 데이터 레코드를 연결하기 위해 사용됩니다.이중 링크 리스트는 다중 링크 리스트의 특수한 경우로 볼 수 있지만, 둘 이상의 순서가 서로 반대이기 때문에 알고리즘이 단순하고 효율적이기 때문에 보통 별도의 경우로 취급됩니다.

순환 링크 리스트

목록의 마지막 노드에서는 링크필드에 늘 참조가 포함되어 있는 경우가 많습니다.특수값은 추가 노드가 없음을 나타냅니다.덜 일반적인 규칙은 목록의 첫 번째 노드를 가리키는 것입니다. 이 경우 목록은 '원형' 또는 '원형 링크'라고 하며, 그렇지 않으면 '개방형' 또는 '선형'이라고 합니다.마지막 포인터가 첫 번째 노드를 가리키는 목록입니다.

순환 링크 리스트

순환 이중 링크 리스트의 경우 첫 번째 노드는 목록의 마지막 노드도 가리킵니다.

Sentinel 노드

일부 구현에서는 첫 번째 데이터 기록 전 또는 마지막 데이터 기록 후에 추가 '센티넬' 또는 '더미' 노드가 추가될 수 있습니다.이 규칙에서는 모든 링크를 안전하게 참조 해제할 수 있고 모든 목록(데이터 요소가 없는 목록도 포함)에 항상 "첫 번째" 및 "마지막" 노드가 있으므로 목록 처리 알고리즘을 단순화하고 가속화합니다.

빈 리스트

빈 목록은 데이터 레코드가 포함되지 않은 목록입니다.이것은 보통 노드가 0이라고 하는 것과 같습니다.Sentinel 노드를 사용하는 경우 일반적으로 목록에 Sentinel 노드만 있으면 목록이 비어 있다고 합니다.

해시 링크

링크 필드는 물리적으로 노드의 일부일 필요는 없습니다.데이터 레코드가 배열에 저장되고 인덱스에 의해 참조되는 경우 링크 필드는 데이터 레코드와 동일한 인덱스로 별도의 배열에 저장될 수 있다.

리스트 핸들

첫 번째 노드에 대한 참조는 목록 전체에 대한 액세스를 제공하기 때문에 해당 참조는 종종 목록의 '주소', '포인트', 또는 '핸들'이라고 불립니다.링크 리스트를 조작하는 알고리즘에서는, 통상, 이러한 핸들을 입력 리스트로 가져와서, 그 핸들을 결과 리스트로 되돌립니다.실제로 이러한 알고리즘의 맥락에서 "list"라는 단어는 종종 "list handle"을 의미합니다.단, 상황에 따라서는 첫 번째 노드와 마지막 노드를 가리키는 2개의 링크로 구성된 핸들별로 목록을 참조하는 것이 편리할 수 있습니다.

대안을 조합하다

위에 열거된 대안은 거의 모든 방법으로 임의로 조합될 수 있으므로, 보초병 없이 순환 이중 링크된 목록, 보초병과의 순환 단일 링크된 목록 등이 있을 수 있습니다.

트레이드오프

컴퓨터 프로그래밍과 설계에서 대부분의 선택사항이 그렇듯이 모든 상황에 잘 맞는 방법은 없습니다.링크된 목록 데이터 구조는 어떤 경우에는 잘 작동하지만 다른 경우에는 문제가 발생할 수 있습니다.링크된 목록 구조와 관련된 몇 가지 공통적인 트레이드오프 목록입니다.

링크 리스트와 다이내믹 어레이

목록 데이터 구조 비교
	훔쳐보다 (인덱스)	변환(삽입 또는 삭제)			여유 공간, 평균
	훔쳐보다 (인덱스)	시작	끝.	가운데	여유 공간, 평균
링크 리스트	θ(n)	θ(1)	δ(1), 알려진 엔드 요소 δ(n), 알 수 없는 엔드 요소	Peek 시간 + θ(1)^[4]^[5]	θ(n)
어레이	θ(1)	—	—	—	0
다이내믹 어레이	θ(1)	θ(n)	θ(1)상각	θ(n)	θ(^[6]n)
밸런스 트리	δ(로그 n)	δ(로그 n)	δ(로그 n)	δ(로그 n)	θ(n)
랜덤 액세스리스트	δ(^[7]로그 n)	θ(1)	--^[7]	--^[7]	θ(n)
해시 어레이 트리	θ(1)	θ(n)	θ(1)상각	θ(n)	θ(nn)

동적 배열은 모든 요소를 메모리에 연속적으로 할당하고 현재 요소 수를 유지하는 데이터 구조입니다.다이내믹 어레이용으로 예약된 공간을 초과하면 해당 영역이 재할당되고 (가능성이 있는) 복사되므로 비용이 많이 듭니다.

링크 목록은 동적 배열에 비해 몇 가지 이점이 있습니다.리스트의 특정 포인트에 요소를 삽입 또는 삭제하는 것은 노드에 대한 포인터를 이미 인덱싱했다고 가정할 때(삭제할 포인터의 이전 또는 삽입점의 이전) 상시 작업입니다(그렇지 않으면 이 참조가 없으면 O(n)가 됩니다).다이나믹 어레이에 랜덤한 장소에서 삽입하는 경우에는 반을 이동할 필요가 있습니다.f 요소 평균 및 최악의 경우 모든 요소.슬롯을 「빈」이라고 마크하는 것으로, 일정한 시간내에 어레이로부터 요소를 「삭제」할 수 있습니다만, 이로 인해 반복의 퍼포먼스가 방해되는 단편화가 발생합니다.

또, 링크 리스트에 임의로 많은 요소를 삽입할 수 있습니다.다이나믹 어레이는 최종적으로 기반이 되는 어레이의 데이터 구조를 가득 채우고 재할당해야 합니다.이 작업은 메모리가 단편화되어도 재할당 비용이 발생할 수 있습니다.재할당으로 인한 삽입 비용은 O(1)로 상각됩니다.이렇게 하면 어레이 끝에 요소를 추가할 수 있지만, 중간 위치에 삽입(또는 분리)할 경우 인접성을 유지하기 위해 데이터가 이동하기 때문에 여전히 막대한 비용이 발생합니다.많은 요소가 제거된 어레이는 너무 많은 공간을 낭비하지 않도록 크기를 조정해야 할 수도 있습니다.

반면 동적 배열(및 고정 크기 배열 데이터 구조)은 일정한 시간 랜덤 액세스를 허용하지만 링크된 목록은 요소에 대한 순차적 액세스만 허용합니다.실제로 단일 링크 리스트는 한 방향으로만 쉽게 이동할 수 있습니다.따라서 링크된 목록은 힙소트와 같이 인덱스로 요소를 빠르게 검색하는 데 유용한 응용 프로그램에 적합하지 않습니다.어레이 및 동적 어레이에 대한 순차적 액세스도 많은 머신에 있는 링크드 리스트보다 빠릅니다.이는 참조 위치가 최적화되어 데이터 캐싱을 효율적으로 활용하기 때문입니다.

링크 리스트의 또 다른 단점은 참조에 필요한 추가 스토리지입니다.이러한 경우 링크의 스토리지 오버헤드가 데이터 크기의 2배 이상 초과될 수 있기 때문에 문자나 부울값과 같은 작은 데이터 항목 목록에 사용할 수 없습니다.반면 동적 어레이는 데이터 자체를 위한 공간(및 매우 적은 양의 제어 데이터)^{[note 1]}만 필요로 합니다.또, 새로운 요소 마다 개별적으로 메모리를 할당하는 것이 느리고, 순진한 할당으로 낭비가 되는 일이 있습니다.이 문제는 일반적으로 메모리 풀을 사용하여 해결됩니다.

일부 하이브리드 솔루션은 두 가지 표현의 장점을 결합하려고 합니다.롤링되지 않은 링크 목록은 각 목록 노드에 여러 요소를 저장하여 참조용 메모리 오버헤드를 줄이면서 캐시 성능을 향상시킵니다.CDR 코딩은 참조를 참조 레코드의 끝부분에서 확장되는 실제 참조 데이터로 대체함으로써 이 두 가지를 모두 수행합니다.

동적 배열과 링크 목록 사용의 장단점을 강조하는 좋은 예는 Josephus 문제를 해결하는 프로그램을 구현하는 것입니다.요세푸스 문제는 한 무리의 사람들을 둥글게 서게 하는 선거 방식이다.소정의 인물부터 시작하여 원 둘레를 n회 카운트할 수 있다.n번째 인물에 도달하면 원에서 제거하고 회원들에게 원을 닫게 해야 한다.이 과정은 한 사람만 남을 때까지 반복된다.그 사람이 선거에서 이겼어요.이는 링크 리스트와 동적 배열의 장단점을 보여줍니다.왜냐하면 사용자를 순환 링크 리스트에서 연결된 노드로 볼 경우 링크 리스트가 노드를 얼마나 쉽게 삭제할 수 있는지를 보여주기 때문입니다(다른 노드로의 링크 재배열만 하면 되기 때문입니다.그러나 링크된 목록은 삭제할 다음 사용자를 찾을 수 없으며 해당 사용자를 찾을 때까지 목록을 검색해야 합니다.반면 다이내믹 어레이는 노드(또는 요소)를 삭제할 때 모든 요소를 개별적으로 목록 위로 이동하지 않으면 노드를 삭제할 수 없기 때문에 노드(또는 요소)를 삭제할 수 없습니다.단, 배열 내의 위치에 따라 원 내의 n번째 인물을 직접 참조하면 예외적으로 쉽게 찾을 수 있습니다.

목록 순위 문제는 링크된 목록 표현을 배열로 효율적으로 변환하는 것과 관련이 있습니다.기존 컴퓨터에게는 사소한 일이지만 병렬 알고리즘으로 이 문제를 해결하는 것은 복잡하고 많은 연구의 주제가 되어 왔다.

밸런스 트리는 메모리 액세스 패턴과 링크 리스트와 같은 공간 오버헤드를 가지며, 랜덤 액세스에 O(n)가 아닌 O(log n) 시간이 걸리는 훨씬 효율적인 인덱싱을 가능하게 합니다.그러나 균형을 유지하기 위한 트리 조작의 오버헤드로 인해 삽입 및 삭제 작업이 더 많이 소요됩니다.트리가 자동으로 균형 상태를 유지하는 방식이 있습니다.AVL 트리 또는 빨간색-검은색 트리.

단일 링크된 선형 목록과 다른 목록 비교

이중 링크 리스트와 순환 리스트는 단일 링크된 선형 리스트보다 장점이 있지만, 선형 리스트는 상황에 따라 선호되는 몇 가지 이점을 제공합니다.

단일 링크 선형 목록은 동일한 유형의 더 작은 개체에 대한 포인터를 포함하므로 재귀 데이터 구조입니다.따라서 단일 링크된 선형 목록의 많은 연산(예: 두 목록을 병합하거나 요소를 역순으로 열거)에는 반복 명령을 사용하는 어떤 솔루션보다 훨씬 단순한 재귀 알고리즘이 있는 경우가 많습니다.이러한 재귀적 솔루션은 이중으로 연결된 목록과 순환적으로 연결된 목록에 적응할 수 있지만, 절차에는 일반적으로 추가 인수와 더 복잡한 기본 사례가 필요합니다.

선형 단일 링크 리스트에서는 테일 공유도 가능합니다.이것은, 2개의 다른 리스트의 단말 부분으로서 서브 리스트의 공통의 최종 부분을 사용하는 것입니다.특히 목록의 선두에 새 노드가 추가되면 이전 목록은 새 노드의 꼬리 부분으로서 사용할 수 있습니다.이것은 영속적인 데이터 구조의 단순한 예입니다.다른 변형에서는 그렇지 않습니다.노드는 2개의 서로 다른 원형 또는 이중 링크 목록에 속하지 않을 수 있습니다.

특히 엔드센티넬 노드는 단일 링크된 비원형 리스트 간에 공유할 수 있다.이러한 모든 목록에 동일한 엔드 센티넬 노드를 사용할 수 있습니다.예를 들어 리스프에서는 모든 적절한 리스트는 다음과 같은 특별한 노드에 대한 링크로 끝납니다.nil또는(),누구의.CAR그리고.CDR링크는 자신을 가리킵니다.따라서 리스프 절차는 안전하게CAR또는CDR모든 리스트에서.

화려한 변형의 장점은 종종 알고리즘의 효율이 아닌 복잡성으로 제한됩니다.특히 순환 목록은 보통 첫 번째 및 마지막 노드를 가리키는 두 변수와 함께 추가 비용 없이 선형 목록으로 에뮬레이트할 수 있습니다.

이중 링크 대 단일 링크

이중 링크 리스트는 노드당 더 많은 공간을 필요로 하며(XOR 링크를 사용하지 않는 한), 기본 운영 비용이 더 많이 듭니다. 그러나 양방향으로 목록에 빠르고 쉽게 순차적으로 액세스할 수 있기 때문에 대부분의 경우 조작이 더 쉽습니다.이중 링크 리스트에서는, 그 노드의 주소만이 주어진 일정한 수의 조작으로 노드를 삽입 또는 삭제할 수 있습니다.단일 링크 목록에서 동일한 작업을 수행하려면 해당 노드에 대한 포인터의 주소가 필요합니다.이 주소는 목록 전체의 핸들(첫 번째 노드의 경우) 또는 이전 노드의 링크필드 중 하나입니다.일부 알고리즘은 양방향으로 액세스해야 합니다.반면 이중 링크 리스트는 테일 공유를 허용하지 않으며 영구 데이터 구조로 사용할 수 없습니다.

순환 링크와 선형 링크

순환 링크 리스트는 폴리곤의 모서리, FIFO("선입선출") 순서로 사용되고 해방되는 버퍼 풀, 라운드 로빈 순서로 시간 공유해야 하는 일련의 프로세스 등 자연스럽게 원형인 어레이를 나타내는 자연스러운 옵션일 수 있습니다.이러한 응용 프로그램에서는 임의의 노드에 대한 포인터가 목록 전체의 핸들 역할을 합니다.

순환 목록을 사용하면 마지막 노드에 대한 포인터가 하나의 링크를 따라 첫 번째 노드에 쉽게 액세스할 수 있습니다.따라서 목록의 양 끝에 대한 액세스를 필요로 하는 애플리케이션(예: 큐의 구현)에서 순환 구조는 두 개의 포인터가 아닌 하나의 포인터로 구조를 처리할 수 있도록 합니다.

순환 리스트는, 각 피스의 마지막 노드의 주소를 지정함으로써, 일정 시간내에 2개의 순환 리스트로 분할할 수 있다.이 조작은 이들 2개의 노드의 링크필드의 내용을 스왑하는 것으로 구성됩니다.2개의 서로 다른 목록 중 임의의 2개의 노드에 동일한 작업을 적용하면 2개의 목록이 하나로 결합됩니다.이 속성은 쿼드 엣지 및 페이스 엣지 등 일부 알고리즘과 데이터 구조를 대폭 간소화합니다.

빈 순환 목록(이러한 것이 타당할 경우)의 가장 간단한 표현은 늘 포인터이며 목록에 노드가 없음을 나타냅니다.이 옵션을 선택하지 않으면 많은 알고리즘이 이 특수한 경우에 대해 테스트하고 별도로 처리해야 합니다.반면 빈 선형 목록을 나타내기 위해 null을 사용하는 것이 더 자연스럽고 특별한 경우가 거의 없습니다.

일부 응용 프로그램에서는 원형과 선형 또는 선형 초기 세그먼트와 함께 원형으로 다를 수 있는 단일 링크 목록을 사용하면 유용합니다.이들 알고리즘에서 검색 또는 기타 동작을 하는 알고리즘은 실수로 무한 루프에 들어가지 않도록 주의해야 합니다.일반적인 방법 중 하나는 두 번째 포인터가 목록의 절반 또는 두 배의 속도로 이동하도록 하는 것입니다. 두 포인터가 같은 노드에서 만나면 사이클을 찾은 것입니다.

감시 노드 사용

Sentinel 노드는 모든 요소에 대해 다음 노드 또는 이전 노드가 존재하며 빈 목록에도 적어도1개의 노드가 있음을 확인함으로써 특정 목록 조작을 단순화할 수 있습니다.또한 목록 끝에 적절한 데이터 필드가 있는 감시 노드를 사용하여 일부 목록 종료 테스트를 제거할 수도 있습니다.예를 들어 지정된 값이 x인 노드를 찾는 목록을 스캔할 때 Sentinel의 데이터 필드를 x로 설정하면 루프 내에서 목록 종료 테스트를 수행할 필요가 없습니다.다른 예로는 정렬된2개의 리스트의 Marge가 있습니다.Sentinel의 데이터 필드가 +'로 설정되어 있는 경우 다음 출력 노드를 선택할 때 빈 목록을 특별히 처리할 필요가 없습니다.

단, Sentinel 노드는 (특히 많은 쇼트리스트를 사용하는 어플리케이션의 경우) 여분의 공간을 소비하여 다른 조작(빈 리스트의 신규 작성 등)을 복잡하게 할 수 있습니다.

그러나 순환 목록을 단순히 선형 목록을 시뮬레이션하는 데 사용할 경우 마지막 데이터 노드와 첫 번째 데이터 노드 사이에 모든 목록에 단일 Sentinel 노드를 추가하면 이러한 복잡성을 어느 정도 피할 수 있습니다.이 표기법에서는 빈 리스트는 다음 노드링크를 통해 자신을 가리키는 센티넬노드만으로 구성됩니다.리스트 핸들은 목록이 비어 있지 않은 경우 Sentinel 이전 마지막 데이터 노드에 대한 포인터이거나 목록이 비어 있는 경우 Sentinel 자체에 대한 포인터여야 합니다.

동일한 트릭을 사용하여 이중 링크된 선형 목록을 단일 감시 노드가 있는 순환 이중 링크 목록으로 변환함으로써 처리 작업을 단순화할 수 있습니다.단, 이 경우 핸들은 더미 노드 ^[8]자체에 대한 단일 포인터여야 합니다.

링크 리스트 조작

링크된 목록을 일괄적으로 조작할 때는 이전 할당에서 비활성화된 값을 사용하지 않도록 주의해야 합니다.이로 인해 링크 목록 노드 삽입 또는 삭제 알고리즘이 다소 미묘해집니다.이 섹션에서는 단일, 이중 및 순환 링크목록에서 노드를 추가 또는 삭제하기 위한 의사 코드에 대해 설명합니다.목록 종료 마커 또는 Sentinel을 참조하기 위해 null을 사용합니다.이 마커 또는 Sentinel은 여러 가지 방법으로 구현될 수 있습니다.

선형 링크 리스트

단일 링크 리스트

노드 데이터 구조에는 두 개의 필드가 있습니다.또한 항상 목록의 첫 번째 노드를 가리키거나 빈 목록에 대해서는 늘인 변수 firstNode도 유지합니다.

record Node { data ; // 노드에 저장되는 데이터 // 다음^[2] 노드에 대한 참조, 마지막 노드에 대한 null}

레코드 목록 {Node firstNode // 목록의 첫 번째 노드를 가리키며 빈 목록은 null입니다.}

단일 링크 리스트의 트래버설은 첫 번째 노드에서 시작하여 다음 각 링크를 끝까지 따라가는 간단한 방법입니다.

node : = 목록.노드가 null이 아닌 동안 firstNode(node.data로 작업): 노드:= node.next

다음 코드는 단일 링크 목록에서 기존 노드 뒤에 노드를 삽입합니다.이 다이어그램은 작동 방식을 보여 줍니다.기존 노드 앞에 노드를 직접 삽입할 수 없습니다.대신 이전 노드를 추적하여 노드 뒤에 노드를 삽입해야 합니다.

단일 링크 목록에 노드를 삽입하는 다이어그램

함수 insertAfter(노드 노드, 노드 newNode) // 노드 newNode 뒤에 newNode를 삽입합니다. next : = node . next node . next : = newNode

목록 시작 부분에 삽입하려면 별도의 기능이 필요합니다.이를 위해서는 firstNode를 업데이트해야 합니다.

insertBeginning(목록, Node newNode) // 현재 첫 번째 노드 newNode.next := 목록 앞에 노드를 삽입합니다.firstNode 목록.firstNode : = newNode

마찬가지로 특정 노드 뒤에 노드를 삭제하고 목록의 선두에서 노드를 삭제하는 기능도 있습니다.이 그림은 전자를 예시하고 있다.특정 노드를 찾아 삭제하려면 이전 요소를 다시 추적해야 합니다.

단일 링크 목록에서 노드 삭제 다이어그램

함수 removeAfter(노드 노드) // 이 하나의 사용되지 않는 노드:= 노드.next 노드.next := 노드.next.next가 사용되지 않는 노드를 삭제합니다.

removeBeginning(목록) // 첫 번째 노드 undoeseNode := 목록을 삭제합니다.firstNode 목록.firstNode : = 목록.firstNode.next // 삭제된 노드를 포인트하면 폐기됩니다.

주의해 주세요removeBeginning()놓다list.firstNode로.null목록 내 마지막 노드를 삭제합니다.

역방향으로 반복할 수 없기 때문에 효율적입니다.insertBefore또는removeBefore작업을 수행할 수 없습니다.특정 노드보다 먼저 목록에 삽입하려면 목록을 통과해야 합니다. 최악의 경우 실행 시간은 O(n)입니다.

링크된 목록을 다른 목록에 추가하는 것은 테일 참조가 목록 구조의 일부로 유지되지 않는 한 비효율적일 수 있습니다. 꼬리를 찾으려면 첫 번째 목록 전체를 이동한 다음 여기에 두 번째 목록을 추가해야 하기 때문입니다.따라서 2개의 선형 링크 리스트가 각각 $길이$ n(\ $displaystyle$ n $n$ 인 경우 list appending의 시간 $O(n)$ 는 O $O(n)$ )(\ $displaystyle$ O $(n$ 입니다.Lisp 계열의 언어에서는 list appending은 list appending에 의해 제공됩니다.append절차.

리스트의 선두에 더미 요소를 포함시킴으로써 링크된 리스트 조작의 특수한 케이스의 많은 부분을 제거할 수 있다.이것에 의해, 리스트의 선두에 특별한 케이스가 없는 것을 보증해, 양쪽 모두를 렌더링 할 수 있습니다.insertBeginning()그리고.removeBeginning()불필요.이 경우 목록의 첫 번째 유용한 데이터는 다음 위치에서 찾을 수 있습니다.list.firstNode.next.

순환 링크 리스트

순환 링크 리스트에서는 null을 사용하지 않고 모든 노드가 연속된 원으로 링크됩니다.전면과 후면(큐 등)이 있는 목록의 경우 목록의 마지막 노드에 대한 참조가 저장됩니다.마지막 노드 뒤의 다음 노드가 첫 번째 노드입니다.일정 시간 내에 목록 뒤에 요소를 추가하고 앞에서 제거할 수 있습니다.

순환 링크 리스트는 단일 또는 이중으로 링크할 수 있습니다.

두 유형의 순환 링크 목록은 모두 지정된 노드에서 시작하여 전체 목록을 이동할 수 있는 기능을 제공합니다.이렇게 하면 종종 firstNode와 lastNode의 저장을 피할 수 있습니다.다만, 리스트가 비어 있는 경우는 lastNode 변수, 비어 있는 경우는 null 변수 등, 빈 리스트에 대한 특별한 표현이 필요합니다.여기에서는 이러한 lastNode를 사용합니다.이 표현을 사용하면 빈 목록이 아닌 노드의 추가 및 삭제가 대폭 간소화되지만 빈 목록은 특수한 경우입니다.

알고리즘

someNode가 비어 있지 않은 원형 단일 링크 목록의 일부 노드라고 가정하면 이 코드는 someNode로 시작하는 목록에서 반복됩니다.

function if someNode ≠ null node : = someNode가 node.value node : = node . next with node some someNode로 작업을 수행하는 경우 반복(someNode)

테스트 "while node "some Node"는 루프의 끝에 있어야 합니다.테스트를 루프의 선두로 이동했을 경우 목록에 노드가1개만 있을 때마다 절차는 실패합니다.

이 함수는 특정 노드 "node" 뒤에 노드 "newNode"를 순환 링크 목록에 삽입합니다."node"가 null일 경우 목록이 비어 있는 것으로 간주됩니다.

노드 = null인 경우 insertAfter(노드 노드, 노드 newNode). next : = newNode else newNode. next : = node . next : next : = newNode update lastNode 변수(필요한 경우)

"L"이 순환 링크 목록의 마지막 노드를 가리키는 변수라고 가정합니다(또는 목록이 비어 있는 경우에는 null).목록 끝에 "new node"를 추가하려면 다음을 수행합니다.

insertAfter(L, newNode) L : = newNode

리스트의 선두에 「new Node」를 삽입하려면 , 다음의 조작을 실시합니다.

L = null L : = newNode인 경우 삽입 후(L, newNode)

이 함수는 O(1) 시간의 특정 노드 "node" 앞에 값 "newVal"을 삽입합니다."node"와 다음 노드 사이에 새 노드를 생성하고 "node" 값을 새 노드에 입력한 후 "newVal"을 "node"에 넣습니다.따라서 firstNode 변수만 있는 단일 링크된 순환 링크 목록은 O(1) 시간 내에 앞뒤에 삽입할 수 있습니다.

노드 = null인 경우 insertBefore(노드 노드, newVal) 함수 insertBefore(노드, newVal) // 목록이 빈 newNode:= newNode(데이터:= newVal, next:= newNode) 또는 newNode:= newNode:= newNode.next.node.next.node.node.node.node.node.node.node.node.node.now node.node.node.node.node.node.node.

이 함수는 O(1) 시간 내에 크기가 1보다 큰 목록에서 Null이 아닌 노드를 제거합니다.다음 노드에서 노드로 데이터를 복사하고 노드의 다음 포인터를 설정하여 다음 노드를 건너뜁니다.

노드가 null이고 목록 크기 > 1이면 함수 제거(노드)가 수행됨데이터 : = node . data node . node . next . data node . next = node . next . next . node . next . next . next . node . next . returnedData

노드 배열을 사용한 링크 리스트

어떤 유형의 참조도 지원하지 않는 언어도 포인터를 배열 인덱스로 대체하여 링크를 생성할 수 있습니다.이 방법은 레코드 배열을 유지하는 것입니다.여기서 각 레코드에는 배열 내의 다음(및 이전) 노드의 인덱스를 나타내는 정수 필드가 있습니다.어레이의 모든 노드를 사용할 필요는 없습니다.레코드도 지원되지 않는 경우 병렬 어레이를 대신 사용할 수 있습니다.

예를 들어 포인터 대신 배열을 사용하는 다음 링크 목록 레코드를 고려하십시오.

{ integer next }, // 어레이 정수 prev의 다음 항목 인덱스, // 이전 항목(이중 링크된 경우) 문자열 이름, 실제 균형, }을(를)

링크 리스트는 이들 구조의 배열과 첫 번째 요소의 인덱스를 저장하기 위한 정수 변수를 작성함으로써 구축될 수 있다.

정수 리스트헤드 엔트리 레코드 [1000]

요소 간의 링크는 지정된 요소 내의 다음(또는 이전) 셀의 배열 인덱스를 [Next]필드 또는 [Prev]필드에 배치함으로써 형성됩니다.예를 들어 다음과 같습니다.

색인	다음 분.	프리브	이름.	균형.
0	1	4	존스, 존	123.45
1	−1	0	스미스, 조셉	234.56
2 (list Head)	4	−1	애덤스	0.00
3			무시해, 이그나티우스	999.99
4	0	2	또 다른 아니타	876.54
5
6
7

위의 예에서는ListHead는 목록의 첫 번째 엔트리의 위치인2 로 설정됩니다.엔트리 3 및5 ~ 7은 리스트에 포함되지 않습니다.이러한 셀은 목록에 추가할 때 사용할 수 있습니다.를 작성함으로써ListFree사용 가능한 셀을 추적하기 위해 자유 목록을 작성할 수 있습니다.모든 엔트리가 사용 중인 경우 목록에 새 엔트리를 저장하기 전에 어레이 크기를 늘리거나 일부 요소를 삭제해야 합니다.

다음 코드는 목록을 통과하여 이름과 계정 잔액을 표시합니다.

i : = 목록i 0 0 // 목록 인쇄 i, 레코드 [i]를 루프하는 동안 헤딩합니다.이름, 레코드[i]balance // print entry i : = Records [ i ]를 선택합니다.다음 분.

선택지에 직면했을 때, 이 어프로치의 장점은 다음과 같습니다.

링크 리스트는 재배치할 수 있습니다.즉, 메모리 내에서 자유롭게 이동할 수 있습니다.또, 디스크상의 스토리지나 네트워크를 개입시켜 전송하기 위해서, 신속하고 직접 시리얼화할 수도 있습니다.
특히 목록이 적은 경우 어레이 인덱스는 많은 아키텍처에서 풀 포인터보다 훨씬 적은 공간을 차지할 수 있습니다.
레퍼런스 인접성은 노드를 메모리에 함께 보관하고 정기적으로 재배치함으로써 향상될 수 있지만, 이는 일반 스토어에서도 가능합니다.
Nave 동적 메모리 할당자는 할당된 각 노드에 대해 과도한 양의 오버헤드 스토리지를 생성할 수 있습니다.이 접근법에서는 노드당 할당 오버헤드가 거의 발생하지 않습니다.
일반적으로 동적 메모리 할당에는 원하는 크기의 빈 메모리 블록을 검색해야 하므로 미리 할당된 어레이에서 엔트리를 캡처하는 것은 각 노드에 대해 동적 메모리 할당을 사용하는 것보다 빠릅니다.

단, 이 방법에는 노드 전용 메모리 공간을 만들고 관리한다는 단점이 있습니다.이로 인해 다음과 같은 문제가 발생합니다.

구현이 복잡해집니다.
대용량 어레이가 가득 차면 확장하기가 어렵거나 불가능할 수 있지만, 대규모 일반 메모리 풀에서 새로운 링크 목록 노드를 위한 공간을 찾는 것은 더 쉬울 수 있습니다.
동적 배열에 요소를 추가하면(완전할 경우) 상각된 상수이지만) 일정 시간이 아닌 선형(O(n)이 예기치 않게 걸릴 수 있습니다.
목록이 예상보다 작거나 사용 가능한 노드가 많은 경우 일반 메모리 풀을 사용하면 다른 데이터에 더 많은 메모리가 남습니다.

이러한 이유로 이 접근법은 주로 동적 메모리 할당을 지원하지 않는 언어에 사용됩니다.어레이를 생성할 때 목록의 최대 크기를 알 수 있는 경우에도 이러한 단점이 완화됩니다.

언어 지원

Lisp나 Scheme와 같은 많은 프로그래밍 언어에는 단일 링크 목록이 내장되어 있습니다.많은 기능 언어에서 이러한 목록은 노드로부터 구성되며, 각각 cons 또는 cons cell이라고 불립니다.단점에는 2개의 필드(car, 해당 노드의 데이터에 대한 참조)와 다음 노드에 대한 참조인 cdr)가 있습니다.다른 데이터 구조를 구축하기 위해 콘셀을 사용할 수 있지만 이것이 주된 목적입니다.

추상 데이터 유형 또는 템플릿을 지원하는 언어에서는 링크 목록 ADT 또는 템플릿을 링크 목록 구축에 사용할 수 있습니다.다른 언어에서 링크 리스트는 일반적으로 레코드와 함께 참조를 사용하여 작성됩니다.

내부 및 외부 스토리지

링크된 목록을 구성할 때 목록의 데이터를 링크된 목록 노드(내부 스토리지라고 함)에 직접 저장할지 또는 단순히 외부 스토리지라고 함)에 대한 참조를 저장할지 선택해야 합니다.내부 스토리지는 데이터에 대한 액세스를 보다 효율적으로 하고, 전체적으로 필요한 스토리지를 줄이고, 참조 위치를 개선하며, 목록에 대한 메모리 관리를 단순화할 수 있는 장점이 있습니다(데이터는 목록 노드와 동시에 할당 및 할당 해제).

반면 외부 스토리지는 데이터의 크기에 관계없이 링크 목록에 동일한 데이터 구조와 기계 코드를 사용할 수 있다는 점에서 보다 범용적이라는 장점이 있습니다.또한 동일한 데이터를 여러 링크 목록에 쉽게 배치할 수 있습니다.내부 스토리지에서는 노드 데이터 구조에 여러 다음 참조를 포함시킴으로써 동일한 데이터를 여러 목록에 배치할 수 있지만, 각 필드에 따라 셀을 추가하거나 삭제하는 별도의 루틴을 만들어야 합니다.외부 스토리지를 사용하여 내부 스토리지를 사용하는 요소의 추가 링크 리스트를 작성할 수 있으며, 추가 링크 리스트의 셀에 데이터를 포함하는 링크 리스트의 노드에 대한 참조를 저장할 수 있습니다.

일반적으로 일련의 데이터 구조를 링크 목록에 포함해야 하는 경우 외부 스토리지가 최선의 접근 방식입니다.데이터 구조 집합을 하나의 연결 목록에 포함해야 하는 경우 외부 스토리지를 사용하는 일반 연결 목록 패키지를 사용할 수 없는 한 내부 스토리지가 약간 더 낫습니다.마찬가지로 동일한 데이터 구조에 저장할 수 있는 서로 다른 데이터 세트를 단일 링크 목록에 포함할 경우 내부 스토리지로도 충분합니다.

일부 언어에서 사용할 수 있는 또 다른 접근법은 서로 다른 데이터 구조를 사용하는 것이지만, 모두 같은 위치에 다음(및 이중 링크 리스트의 경우 사전) 참조를 포함한 초기 필드가 있습니다.각 데이터 유형에 대해 개별 구조를 정의한 후, 다른 모든 구조에서 공유되는 최소 양의 데이터를 포함하는 일반 구조를 정의할 수 있으며 구조의 맨 위(시작)에 포함할 수 있습니다.그런 다음 최소 구조를 사용하여 링크된 목록 유형 작업을 수행하는 일반 루틴을 만들 수 있지만 개별 루틴이 특정 데이터를 처리할 수 있습니다.이 접근법은 여러 유형의 메시지를 수신하는 메시지 해석 루틴에서 자주 사용됩니다.다만, 모두 같은 필드 세트(통상은 메시지타입의 필드를 포함한다)로 시작합니다.일반 루틴은 수신 시 새로운 메시지를 큐에 추가하고 메시지를 처리하기 위해 큐에서 삭제하기 위해 사용됩니다.그런 다음 메시지 유형 필드를 사용하여 올바른 루틴을 호출하여 특정 유형의 메시지를 처리합니다.

내부 및 외부 스토리지 예시

가족 및 가족 구성원의 연결된 목록을 작성하려고 합니다.내부 스토리지를 사용하는 경우 구조는 다음과 같습니다.

레코드 멤버 {// 다음 패밀리 멤버, 문자열 firstName, 정수 에이징, } 레코드 패밀리 {// 패밀리 자체 다음 패밀리, 문자열 성, 문자열 주소, 멤버 // 이 패밀리 멤버 목록 머리}

내장 스토리지를 사용하여 가족 및 가족 구성원의 전체 목록을 인쇄하려면 다음과 같이 쓸 수 있습니다.

aFamily : = Familys // family 목록부터 시작하며 aFamily // null // loop to family : = aFamily . members // loop to print the member : = aFamily : = aFamily . member . members nextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnext nextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextnextmily : = a Family . next

외부 스토리지를 사용하여 다음과 같은 구조를 작성합니다.

레코드 노드 {/ 일반 링크 구조 노드 다음, 포인터 데이터 // 노드 } 레코드 멤버 {// 패밀리 멤버 문자열 firstName; 정수 연령 } 레코드 패밀리 {// 패밀리 문자열 lastName; 문자열 주소; 노드 멤버 // 이 패밀리 멤버 목록 머리}

외장 스토리지를 사용하여 가족 및 가족 구성원의 전체 목록을 인쇄하려면 다음과 같이 쓸 수 있습니다.

famNode : = 패밀리는 // 패밀리목록에서 시작되지만 famNode null null // 패밀리 aFamily : = ( family ) famNode . data // 패밀리 인쇄 정보에서 패밀리 목록을 추출하는 동안 memNode : = aFamily . member : ≠ //nodenode // //=≠ // // // loop loop ≠ inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform : inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform inform informemNode.data // 멤버 memNode := memNode.next famNode := famNode.next에 대한 노드 인쇄 정보에서 멤버를 추출합니다.

외부 스토리지를 사용하는 경우 노드에서 레코드를 추출하여 적절한 데이터 유형으로 캐스팅하려면 추가 단계가 필요합니다.이는 패밀리 목록과 패밀리 내 구성원 목록이 동일한 데이터 구조(노드)를 사용하여 두 개의 연결된 목록에 저장되고 이 언어에는 매개 변수 유형이 없기 때문입니다.

컴파일 시에 멤버가 속할 수 있는 패밀리의 수를 알고 있는 한, 내부 스토리지는 정상적으로 동작합니다.그러나 실행 시에만 특정 수를 알고 있는 임의의 수의 패밀리에 구성원을 포함해야 하는 경우에는 외부 스토리지가 필요합니다.

검색 속도 향상

링크된 목록에서 특정 요소를 찾으려면 정렬된 경우에도 일반적으로 O(n) 시간(선형 검색)이 필요합니다.이는 다른 데이터 구조보다 링크된 목록의 주요 단점 중 하나입니다.위에서 설명한 변형 외에도, 다음은 검색 시간을 향상시키는 두 가지 간단한 방법입니다.

순서가 지정되지 않은 목록에서 평균 검색 시간을 단축하기 위한 간단한 경험적 접근법 중 하나는 요소가 발견되면 단순히 목록의 선두로 이동하는 Move-to-Front 경험법입니다.이 스킴은 간단한 캐시를 작성할 때 편리하기 때문에 가장 최근에 사용한 아이템도 가장 빨리 찾을 수 있습니다.

또 다른 일반적인 접근법은 보다 효율적인 외부 데이터 구조를 사용하여 링크된 목록을 "색인화"하는 것입니다.예를 들어, 요소가 링크된 목록 노드에 대한 참조인 빨간색-검은색 트리 또는 해시 테이블을 구축할 수 있습니다.이러한 인덱스는 단일 목록에 여러 개 빌드할 수 있습니다.단점은 노드를 추가하거나 제거할 때마다(또는 적어도 인덱스를 다시 사용하기 전에) 이러한 인덱스를 업데이트해야 한다는 것입니다.

랜덤 액세스리스트

랜덤 액세스목록은 ^[9]목록 내의 요소를 읽거나 수정하기 위한 고속 랜덤액세스를 지원하는 목록입니다.하나의 가능한 구현은 스큐 바이너리 번호 시스템을 사용하는 스큐 바이너리 랜덤 액세스목록입니다.스큐 바이너리 번호 시스템은 특수한 속성을 가진 트리 목록을 포함합니다.이것에 의해,^[9] 최악의 경우 고정 시간 헤드/소비 연산, 최악의 경우 인덱스에 의한 요소에의 로그 시간 랜덤 액세스가 가능하게 됩니다.랜덤 액세스리스트는 영속적인 데이터 ^[9]구조로서 실장할 수 있습니다.

랜덤 액세스목록은 동일한 O(1) 헤드 ^[9]및 테일 조작을 지원한다는 점에서 불변의 링크목록으로 간주할 수 있습니다.

랜덤 액세스목록에 대한 간단한 확장은 min-list입니다.이 min-list는 (변환의 ^[9]복잡성 없이) 일정 시간 내에^{[clarification needed]} 목록 전체의 최소 요소를 생성하는 추가 작업을 제공합니다.

메모들

^ 다이내믹 어레이에 필요한 제어 데이터의 양은 보통 $K+B*n$ K + $K+B*n$ n { $display style$ K + $B$ * $n$ } $K+B*n$ 입니다. $K$ 서K { $display style$ K }는 $K$ $어레이별$ 상수 $,$ B { $displaystyle$ B}는 $B$ 치수별 상수 $,$ $n$ { $display style$ n $}$ 은 $n$ 치수 수입니다. $(\displaystyle$ K $)$ 와 $K$ B $(\displaystyle$ B $)$ 는 $B$ 보통 10바이트 정도입니다.

레퍼런스

^ Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 547. ISBN 978-0-201-89685-5.
^ ^a ^b "Archived copy". Archived from the original on 2015-09-23. Retrieved 2015-07-31.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
^ "Archived copy" (PDF). Archived from the original (PDF) on 2016-10-01. Retrieved 2021-08-31.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
^ 1일차 기조연설 - Bjarne Stroustrup : GoingNative 2012에서 C++11 Style on GoingNative 45분 또는 44일
^ 수치 계산: kjellkod에서 다시는 코드에 링크 리스트를 사용하지 않는 이유.wordpress.com
^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo
^ ^a ^b ^c Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86–95. doi:10.1145/224164.224187.
^ Ford, William; Topp, William (2002). Data Structures with C++ using STL (Second ed.). Prentice-Hall. pp. 466–467. ISBN 0-13-085850-1.
^ ^a ^b ^c ^d ^e Okasaki, Chris (1995). Purely Functional Random-Access Lists (PS). In Functional Programming Languages and Computer Architecture. ACM Press. pp. 86–95. Retrieved May 7, 2015.

추가 정보

Juan, Angel (2006). "Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book 'Big Java', by CayS. Horstmann)" (PDF). p. 3. Archived from the original (PDF) on 2012-01-06. Retrieved 2011-07-10.
Black, Paul E. (2004-08-16). Pieterse, Vreda; Black, Paul E. (eds.). "linked list". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 2004-12-14.
Antonakos, James L.; Mansfield, Kenneth C., Jr. (1999). Practical Data Structures Using C/C++. Prentice-Hall. pp. 165–190. ISBN 0-13-280843-9.
Collins, William J. (2005) [2002]. Data Structures and the Java Collections Framework. New York: McGraw Hill. pp. 239–303. ISBN 0-07-282379-8.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2003). Introduction to Algorithms. MIT Press. pp. 205–213, 501–505. ISBN 0-262-03293-7.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "10.2: Linked lists". Introduction to Algorithms (2nd ed.). MIT Press. pp. 204–209. ISBN 0-262-03293-7.
Green, Bert F., Jr. (1961). "Computer Languages for Symbol Manipulation". IRE Transactions on Human Factors in Electronics (2): 3–8. doi:10.1109/THFE2.1961.4503292.
McCarthy, John (1960). "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Communications of the ACM. 3 (4): 184. doi:10.1145/367177.367199.
Knuth, Donald (1997). "2.2.3-2.2.5". Fundamental Algorithms (3rd ed.). Addison-Wesley. pp. 254–298. ISBN 0-201-89683-4.
Newell, Allen; Shaw, F. C. (1957). "Programming the Logic Theory Machine". Proceedings of the Western Joint Computer Conference: 230–240.
Parlante, Nick (2001). "Linked list basics" (PDF). Stanford University. Retrieved 2009-09-21.
Sedgewick, Robert (1998). Algorithms in C. Addison Wesley. pp. 90–109. ISBN 0-201-31452-5.
Shaffer, Clifford A. (1998). A Practical Introduction to Data Structures and Algorithm Analysis. New Jersey: Prentice Hall. pp. 77–102. ISBN 0-13-660911-2.
Wilkes, Maurice Vincent (1964). "An Experiment with a Self-compiling Compiler for a Simple List-Processing Language". Annual Review in Automatic Programming. Pergamon Press. 4 (1): 1. doi:10.1016/0066-4138(64)90013-8.
Wilkes, Maurice Vincent (1964). "Lists and Why They are Useful". Proceeds of the ACM National Conference, Philadelphia 1964. ACM (P–64): F1–1.
Shanmugasundaram, Kulesh (2005-04-04). "Linux Kernel Linked List Explained". Retrieved 2009-09-21.

외부 링크

알고리즘 및 데이터 구조 사전의 설명
Stanford University Computer Science Library Linked Lists 소개
Stanford University Computer Science Library 링크드 리스트 문제
데이터 구조 열기 - 3장 - 링크 목록, Pat Morin
여러 링크 목록에 동시에 있는 노드를 갖는다는 아이디어에 대한 특허(특허 부여 전 수십 년 동안 널리 사용되었음을 유의하십시오.

[8] 다이내믹 어레이에 필요한 제어 데이터의 양은 보통 $K+B*n$ K + $K+B*n$ n { $display style$ K + $B$ * $n$ } $K+B*n$ 입니다. $K$ 서K { $display style$ K }는 $K$ $어레이별$ 상수 $,$ B { $displaystyle$ B}는 $B$ 치수별 상수 $,$ $n$ { $display style$ n $}$ 은 $n$ 치수 수입니다. $(\displaystyle$ K $)$ 와 $K$ B $(\displaystyle$ B $)$ 는 $B$ 보통 10바이트 정도입니다.

[knuth-1] Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 547. ISBN 978-0-201-89685-5.

[:0-2] "Archived copy". Archived from the original on 2015-09-23. Retrieved 2015-07-31.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)

[3] "Archived copy" (PDF). Archived from the original (PDF) on 2016-10-01. Retrieved 2021-08-31.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)

[4] 1일차 기조연설 - Bjarne Stroustrup : GoingNative 2012에서 C++11 Style on GoingNative 45분 또는 44일

[5] 수치 계산: kjellkod에서 다시는 코드에 링크 리스트를 사용하지 않는 이유.wordpress.com

[6] Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo

[okasakiComparison-7] Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86–95. doi:10.1145/224164.224187.

[9] Ford, William; Topp, William (2002). Data Structures with C++ using STL (Second ed.). Prentice-Hall. pp. 466–467. ISBN 0-13-085850-1.

[okasaki-10] Okasaki, Chris (1995). Purely Functional Random-Access Lists (PS). In Functional Programming Languages and Computer Architecture. ACM Press. pp. 86–95. Retrieved May 7, 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[note 1]

[8]

[9]

v t 잘 알려진 데이터 구조
종류들	수집 컨테이너.
추상적인	연관 배열 멀티맵 데이터 구조 검색 목록. 스택 큐 더블 엔드 큐 priority 큐 이중 엔드 priority 큐 세트 멀티셋 디조인트 세트
어레이	비트 배열 순환 버퍼 다이내믹 어레이 해시 테이블 해시 어레이 트리 희박 행렬
링크되어 있다	어소시에이션리스트 링크 리스트 스킵 리스트 언롤링된 링크 리스트 XOR 링크 리스트
나무들	B-트리 이진 검색 트리 AA나무 AVL 트리 붉은색-검은색 셀프밸런싱 트리 스플레이 트리 히프 이진 힙 이항 힙 피보나치 힙 R 트리 R* 트리 R+ 트리 힐베르트 R-트리 트리 해시 트리
그래프	이항 결정도 방향 비순환 그래프 지시 비순환 단어 그래프
데이터 구조 목록

Search

링크 리스트

네임스페이스

더

목차

역사

기본 개념과 용어

단일 링크 리스트

이중 링크 리스트

다중 링크 리스트

순환 링크 리스트

Sentinel 노드

빈 리스트

해시 링크

리스트 핸들

대안을 조합하다

트레이드오프

링크 리스트와 다이내믹 어레이

단일 링크된 선형 목록과 다른 목록 비교

이중 링크 대 단일 링크

순환 링크와 선형 링크

감시 노드 사용

링크 리스트 조작

선형 링크 리스트

단일 링크 리스트

순환 링크 리스트

알고리즘

노드 배열을 사용한 링크 리스트

언어 지원

내부 및 외부 스토리지

내부 및 외부 스토리지 예시

검색 속도 향상

랜덤 액세스리스트

관련 데이터 구조

메모들

레퍼런스

추가 정보

외부 링크