Linked-List

Circular Linked List 이는 Linked List의 한 변형으로, 데이터를 저장하고 조직하는 특정한 방식을 제공한다. Circular Linked List(원형 연결 리스트)는 마지막 노드가 첫 번째 노드를 가리키는 연결 리스트의 변형이다. 이 구조에서는 리스트의 끝이 존재하지 않으며, 모든 노드가 연결되어 원을 형성한다. https://www.geeksforgeeks.org/circular-linked-list/ 특징 마지막 노드의 next 포인터가 NULL이 아닌 첫 번째 노드를 가리킨다. 리스트의 어느 노드에서 시작하더라도 모든 노드를 순회할 수 있다. 리스트의 끝과 시작이 연결되어 있어 순환 구조를 가진다. 장점 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리하다. 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 순환적인 데이터 구조를 표현하기에 적합하다. 메모리를 효율적으로 사용할 수 있다. 단점 구현이 단순 연결 리스트보다 복잡하다. 무한 루프에 빠질 가능성이 있어 순회 중단이 어려울 수 있다. 노드 삭제 시 이전 노드를 찾기 위해 전체 리스트를 순회해야 할 수 있다. 응용 Circular Linked List는 다음과 같은 상황에서 유용하게 사용된다: ...

Doubly Linked List Doubly Linked List는 노드들이 양방향으로 연결된 선형 데이터 구조로, 각 노드가 데이터와 이전 노드, 다음 노드를 가리키는 포인터를 포함하고 있다. Doubly Linked List는 각 노드가 데이터와 두 개의 링크 필드를 가지고 있는 있으며, 이 두 개의 링크는 이전 노드(previous node)와 다음 노드(next node)를 가리킨다. 이러한 구조로 인해 리스트의 양방향 순회가 가능해진다. 과 끝(테일)을 모두 가리키는 포인터를 유지한다. 순환 구조: 마지막 노드의 다음 노드는 첫 번째 노드를, 첫 번째 노드의 이전 노드는 마지막 노드를 가리킬 수 있다. 장점 양방향 탐색: 리스트를 앞뒤로 탐색할 수 있어 효율적인 검색이 가능하다. 삽입과 삭제의 효율성: 노드의 삽입과 삭제가 O(1) 시간 복잡도로 수행된다. 리스트 끝에서의 연산: 테일 포인터를 통해 리스트의 마지막 요소에 즉시 접근할 수 있다. 단점 메모리 사용량 증가: 각 노드가 두 개의 포인터를 저장해야 하므로 메모리 사용량이 증가한다. 구현의 복잡성: 단일 연결 리스트에 비해 구현이 더 복잡하다. 삽입과 삭제 시 포인터 조작: 노드 삽입과 삭제 시 여러 포인터를 조작해야 한다. 응용 웹 브라우저의 앞으로/뒤로 탐색 기능 음악 플레이어의 재생 목록 운영 체제의 작업 스케줄링 캐시 구현 복잡한 데이터 구조(예: 그래프)의 기본 구성 요소 동작 원리 삽입: 새 노드를 생성하고 이전 노드와 다음 노드의 포인터를 적절히 조정한다. 삭제: 삭제할 노드의 이전 노드와 다음 노드를 서로 연결하고 해당 노드를 메모리에서 해제한다. 탐색: 헤드나 테일에서 시작하여 원하는 노드를 찾을 때까지 포인터를 따라 이동한다. 구성 요소 노드: 데이터와 이전/다음 노드를 가리키는 두 개의 포인터로 구성된다. 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다. 테일 포인터: 리스트의 마지막 노드를 가리킨다. 구현 방식 JavaScript를 사용한 Doubly Linked List 구현 예시: ...

Skip List Skip List는 정렬된 연결 리스트를 기반으로 하여 빠른 검색, 삽입, 삭제 연산을 지원하는 확률적 데이터 구조이다. Skip List는 여러 레벨의 연결 리스트로 구성된 데이터 구조로, 각 레벨은 그 아래 레벨의 일부 요소를 포함하며, 최하위 레벨은 모든 요소를 포함한다. https://en.wikipedia.org/wiki/Skip_list#/media/File:Skip_list.svg 특징 다중 레벨 구조: 여러 층의 연결 리스트로 구성된다. 확률적 균형: 랜덤화를 통해 구조의 균형을 유지한다. 정렬 상태 유지: 요소들은 정렬된 순서로 유지된다. 장점 빠른 검색: 평균 O(log n) 시간 복잡도로 검색이 가능하다. 효율적인 삽입/삭제: 평균 O(log n) 시간에 삽입과 삭제가 가능하다. 구현의 단순성: 균형 이진 탐색 트리에 비해 구현이 간단하다. 단점 추가 메모리 사용: 여러 레벨의 포인터로 인해 추가 메모리가 필요하다. 확률적 성능: 최악의 경우 O(n) 시간 복잡도가 발생할 수 있다. 응용 데이터베이스 인덱싱: RocksDB와 같은 키-값 저장소에서 사용된다. 메모리 관리: 비휘발성 메모리 최적화에 활용된다. 캐시 구현: 효율적인 캐시 시스템 구축에 사용된다. 동작 원리 검색: 최상위 레벨에서 시작하여 목표 값보다 작은 노드를 따라 이동하고, 큰 값을 만나면 아래 레벨로 내려간다. 삽입: 랜덤하게 레벨을 결정하고, 해당 레벨까지 노드를 생성하여 연결한다. 삭제: 노드를 찾아 모든 레벨에서 제거한다. 구성 요소 노드: 키, 값, 여러 레벨의 다음 노드 포인터를 포함한다. 헤드 노드: 모든 레벨의 시작점 역할을 한다. 레벨: 여러 층의 연결 리스트 구조를 형성한다. 구현 방식 JavaScript를 사용한 Skip List 구현 예시: ...

Array vs. Linked List 데이터 구조는 프로그래밍에서 데이터를 효율적으로 저장하고 관리하기 위한 방법을 제공합니다. 이 중에서도 배열과 연결 리스트는 가장 기본적이면서도 중요한 데이터 구조이다. 두 구조는 서로 다른 특성과 장단점을 가지고 있어 적절한 상황에 맞게 선택해 사용해야 한다. 배열은 인덱스를 통한 빠른 접근과 간단한 구현이 장점이지만, 크기가 고정되어 있고 중간 삽입/삭제가 비효율적이다. 반면 연결 리스트는 동적 크기 조정과 효율적인 삽입/삭제가 장점이지만, 임의 접근이 불가능하고 추가 메모리를 사용한다. 적절한 상황에 맞는 자료구조 선택은 효율적인 프로그램 개발의 핵심이다. 따라서 문제의 특성과 요구사항을 잘 분석하여 최적의 자료구조를 선택해야 한다. 때로는 두 자료구조의 장점을 결합한 하이브리드 접근 방식이나 다른 고급 자료구조를 활용하는 것이 더 나은 해결책이 될 수도 있다. ...