연결리스트
정의
링크된 데이터 구조와 연결하여 추상 데이터 유형인 목록을 구현합니다. 문자 그대로 목록이라고 불리는 데이터 (아래 노드)의 질량을 저장할 때 다음 순서의 데이터가 위치하는 위치를 포함하는 방식으로 데이터를 저장합니다. 예를 들어, 수업 학생의 데이터를 저장하면 각 학생의 개인 정보를 노드로 지정하고 첫 번째 학생의 개인 세부 사항에 두 번째 학생의 개인 세부 사항이 어디에 있는지 보여줄 수 있습니다. 쉽게 생각해보면 비엔나 소시지에서 나온 자료 한 조각을 써야 할 것 같습니다.
배치가 먼저 철회되면 연희 2, 민수 3, 4... 식에 자료가 정리되면 식에 의한 자료와 연결목록이 연결돼 연희, 연희, 민수, 민수 등이 그 뒤를 이었습니다. 따라서 배열과 달리 새로운 재료, 즉 노드를 후면에 연결하거나 일부 노드를 중간에 배치하는 것이 쉽습니다. 그러나 배열에는 데이터 번호가 없으며 연결 관계만 있기 때문에 특정 노드를 호출하는 데 어려움이 있지만 데이터 당 숫자로 특정 재료를 호출하는 것이 편리합니다.
배열에 비해 항법 속도는 일반적으로 감소하며 데이터의 추가 / 삽입 및 삭제는 쉽지만 지속적으로 항해하지 않으므로 특정 위치의 요소에 액세스할 수 없습니다. 검색 또는 정렬을 자주 하면 배열을 추가하고 삭제하면 연결 목록을 사용할 수 있지만 연결 목록으로 시퀀스를 검색할 필요가 없으며 찾을 필요가 있습니다. B + 트리 데이터 구조는 연결 목록에 더미를 추가하는 것과 같은 모양으로 데이터의 추가 / 삭제 / 조회 / 조회 모두를 선호하며 단점은 구현의 복잡성입니다. 물론 데이터베이스와 파일 시스템은 이 B 트리의 구현이기 때문에 직접 구현할 필요는 없습니다.
또한 배치는 크기를 늘리는 단점이 있습니다. 연속 메모리 공간을 할당해야하지만 크기가 증가하면 자체 연속공간을 할당하는 것이 더 어려워집니다. 컴퓨터가 메모리 관리를 위해 페이징 개념을 도입했기 때문에 연속적인 큰 공간을 할당하는 것은 비합리적이지만, 그럼에도 불구하고 배치는 공간 낭비를 방지해야 합니다.
단순 연결 리스트
그것은 다음 노드에 대한 참조 만있는 가장 간단한 연결 목록 형태입니다. 마지막 요소를 찾기 위해 목록의 끝으로 가야하기 때문에 (O (n) 마지막 요소를 별도로 참조하는 참조가있는 형식의 변형도 있습니다. 일반적으로 대기열을 구현할 때 이러한 방법을 사용합니다.
이 데이터 구조는 헤드 노드를 가리키는 주소를 잃어 버리면 더 이상 전체 데이터를 사용할 수 없다는 단점이 있습니다. 다음 노드를 가리키는 주소 중 하나가 잘못되더라도 체인이 끊어진 것처럼 백데이터를 잃어 안정적인 데이터 구조가 아닙니다.
파일 시스템 내에서 FAT 파일 시스템은 파일의 내용 중 일부가 손상되면 파일의 상당 부분을 잃어 버렸고 무작위 액세스 성능이 낮기 때문에 파일 청크를이 간단한 연결 목록과 연결합니다.
이중 연결 리스트
다음 노드에 대한 참조뿐만 아니라 이전 노드에 대한 참조를 함께 언급하면 이중 연결 목록이됩니다. 빠른 후방 검색의 단순한 이점 외에도 단일 이점이 있습니다. 간단한 연결 목록은 현재 [4] 이중 연결 목록에서 현재 노드를 제거하는 것이 훨씬 쉽고, 동시에 현재 가리키는 노드를 제거하지 않고 O (n)로만 지정됩니다. 대신 관리해야할 두 가지 참조가 있으므로 삽입하거나 정렬하면 작업량이 크고 데이터 구조의 크기가 약간 더 큽니다.
단 하나의 연결 목록이 아니라 손상이 더 강합니다. 헤드와 테일 노드가 있는 경우 하나만 가지고 전체 목록을 순찰할 수 있으므로 연결이 끊어진 체인을 복구할 수 있습니다. 단일 연결 목록은 전체 헤드 노드 손실에서 모든 데이터를 손실하며 테일 노드에서 목록 제한이 불가능합니다. 단점은 이러한 보정 알고리즘을 구현하지 않으면 손상에 취약할 것이라는 것입니다. 예를 들어, 다음 포인터가 업데이트된 프리브 포인터를 업데이트하지 않으면 프리브 포인터를 따르는주기에서 도달할 수 없는 잃어버린노드를 생성합니다.
원형 액세스 리스트
간단한 연결 목록의 마지막 요소가 먼저 요소를 가리키면 원형 연결 목록이됩니다. 마찬가지로 이중 연결 목록의 첫 번째 및 끝을 서로 만들 수 있습니다.
이미 할당된 메모리 공간을 제거하고 재 할당할 부담이 없기 때문에 대기열을 구현하는 데 적합한 스트림 버퍼 구현에도 많이 사용됩니다.