연결리스트 요소가 인접한 위치에 저장되지 않고 포인터를 사용하여 연결되는 선형 데이터 구조입니다. Linked List는 일련의 연결된 노드를 형성하며, 각 노드는 다음 노드의 데이터와 주소를 저장합니다.
노드 구조: 연결된 목록의 노드는 일반적으로 두 가지 구성 요소로 구성됩니다.
데이터: 노드와 관련된 실제 값이나 데이터를 보유합니다.
다음 포인터: 시퀀스의 다음 노드의 메모리 주소(참조)를 저장합니다.
머리와 꼬리: 연결된 목록은 목록의 첫 번째 노드를 가리키는 헤드 노드를 통해 액세스됩니다. 목록의 마지막 노드는 목록의 끝을 나타내는 NULL 또는 nullptr을 가리킵니다. 이 노드를 꼬리 노드라고 합니다.
연결된 목록 데이터 구조가 필요한 이유는 무엇입니까?
아래에 나열된 연결 목록의 몇 가지 장점은 이것이 왜 필요한지 이해하는 데 도움이 될 것입니다.
- 동적 데이터 구조: 메모리 크기는 작업 삽입 또는 삭제에 따라 런타임에 할당되거나 할당 해제될 수 있습니다.
- 삽입/삭제 용이성: 요소 삽입 및 삭제는 삽입 및 삭제 후 요소를 이동할 필요가 없고 주소만 업데이트하면 되므로 배열보다 간단합니다.
- 효율적인 메모리 활용: 우리가 알고 있듯이 Linked List는 요구 사항에 따라 크기가 증가하거나 감소하는 동적 데이터 구조이므로 메모리 낭비를 방지할 수 있습니다.
- 구현: 스택, 큐, 그래프, 해시 맵 등과 같은 연결 목록을 사용하여 다양한 고급 데이터 구조를 구현할 수 있습니다.
예:
시스템에서 배열 id[] = [1000, 1010, 1050, 2000, 2040]에 정렬된 ID 목록을 유지하는 경우.
새 ID 1005를 삽입하려면 정렬된 순서를 유지하기 위해 1000 이후의 모든 요소(1000 제외)를 이동해야 합니다.
특별한 기술을 사용하지 않는 한 배열을 삭제하는 데에도 비용이 많이 듭니다. 예를 들어, id[]에서 1010을 삭제하려면 1010 이후의 모든 항목을 이동해야 하기 때문에 너무 많은 작업이 수행되어 코드 효율성에 영향을 미칩니다.
연결리스트의 종류 :
연결리스트에는 크게 세 가지 유형이 있습니다.
- 단일 연결 목록
- 이중 연결 리스트
- 순환 연결 리스트
1. 단일 연결 목록 :
단일 연결 리스트의 각 노드에는 시퀀스의 다음 노드에 대한 참조가 포함됩니다. 단일 연결 리스트의 순회는 정방향으로 수행됩니다.
단일 연결 목록
2. 이중 연결 목록 :
이중 연결 리스트의 각 노드에는 다음 노드와 이전 노드에 대한 참조가 포함됩니다. 이를 통해 정방향 및 역방향 모두 탐색이 가능하지만 역방향 참조를 위한 추가 메모리가 필요합니다.
이중 연결 목록
삼. 순환 연결 리스트 :
순환 연결 리스트에서 마지막 노드는 다시 헤드 노드를 가리키며 순환 구조를 만듭니다. 단일 또는 이중으로 연결될 수 있습니다.
자바스크립트 여러줄 문자열
순환 연결 리스트
연결된 목록에 대한 작업
- 삽입 : 연결된 목록에 새 노드를 추가하려면 기존 노드의 포인터를 조정하여 적절한 순서를 유지해야 합니다. 삽입은 목록의 시작, 끝 또는 임의의 위치에서 수행할 수 있습니다.
- 삭제 : 연결된 목록에서 노드를 제거하려면 삭제된 노드가 남긴 간격을 메우기 위해 이웃 노드의 포인터를 조정해야 합니다. 삭제는 목록의 시작, 끝 또는 임의의 위치에서 수행할 수 있습니다.
- 수색 : 연결된 목록에서 특정 값을 검색하려면 해당 값을 찾거나 목록 끝에 도달할 때까지 헤드 노드에서 목록을 탐색해야 합니다.
연결리스트의 복잡성 분석 :
- 시간 복잡도: O(n)
- 보조 공간: O(n)
연결리스트의 장점
- 동적 크기: 메모리 할당이 런타임에 수행되므로 연결된 목록이 동적으로 늘어나거나 줄어들 수 있습니다.
- 삽입 및 삭제: 연결된 목록에서 요소를 추가하거나 제거하는 것은 특히 큰 목록의 경우 효율적입니다.
- 유연성: 연결된 목록은 인접한 메모리 블록 없이도 쉽게 재구성하고 수정할 수 있습니다.
연결리스트의 단점
- 무작위 액세스: 배열과 달리 연결 목록은 인덱스를 통해 요소에 직접 액세스할 수 없습니다. 특정 노드에 도달하려면 순회가 필요합니다.
- 추가 메모리: 연결 목록은 배열에 비해 포인터를 저장하기 위해 추가 메모리가 필요합니다.
결론:
연결 목록은 동적 메모리 할당과 효율적인 삽입 및 삭제 작업을 제공하는 다목적 데이터 구조입니다. 연결된 목록의 기본을 이해하는 것은 프로그래머나 컴퓨터 과학 애호가에게 필수적입니다. 이러한 지식을 바탕으로 연결된 목록을 구현하여 다양한 문제를 해결하고 데이터 구조 및 알고리즘에 대한 이해를 넓힐 수 있습니다.