연결 리스트(면접을 위한 CS 전공지식 노트)

연결 리스트

연결 리스트

연결 리스트(Linked List)는 컴퓨터 과학 및 프로그래밍에서 중요한 자료 구조 중 하나로, 

데이터 요소의 선형 집합을 표현하는데 사용됩니다. 

연결 리스트는 배열과는 다르게 데이터 요소가 메모리상에 연속적으로 저장되지 않고, 

각 요소가 다음 요소를 가리키는 링크(혹은 포인터)를 사용하여 연결된 구조를 갖습니다. 

이러한 링크로 인해 데이터 요소가 메모리상에서 어디에 저장되는지에 대한 유연성을 제공하며, 

데이터 요소를 삽입, 삭제, 또는 재배열하기가 쉽습니다.

 

연결 리스트 구성 요소 및 특징

노드(Node): 

연결 리스트의 각 요소를 나타내는 단위로 노드라고 불립니다. 

각 노드는 데이터 요소와 다음 노드를 가리키는 포인터(링크)로 이루어져 있습니다.

헤드(Head): 

연결 리스트의 시작 지점을 가리키는 특별한 노드로, 연결 리스트의 첫 번째 노드를 가리킵니다. 

헤드를 통해 연결 리스트에 접근하고 요소를 탐색합니다.

노드 구조: 

각 노드는 데이터 필드(데이터를 저장하는 부분)와 다음 노드를 가리키는 링크 필드로 구성됩니다.

연결 리스트 유형

단일 연결 리스트(Singly Linked List): 

각 노드가 다음 노드를 가리키는 포인터만을 포함하는 구조입니다. 

마지막 노드는 보통 "NULL"이나 "None"을 가리킵니다.

이중 연결 리스트(Doubly Linked List): 

각 노드가 다음 노드뿐만 아니라 이전 노드도 가리키는 포인터를 포함하는 구조입니다. 

이로 인해 양방향으로 탐색이 가능하며, 삽입 및 삭제 연산이 더 효율적입니다.

연결 리스트의 장점은 데이터 요소의 삽입과 삭제가 배열에 비해 효율적이라는 점입니다. 

그러나 데이터 검색이나 인덱스 접근이 배열에 비해 느릴 수 있습니다. 

어떤 종류의 연결 리스트를 사용할지는 작업의 요구 사항에 따라 다르며, 

연결 리스트는 동적 크기 조절, 스택, 큐, 그래프 등 다양한 응용 프로그램에서 사용됩니다.

 

연결 리스트 주요 사용 사례와 예시

동적 크기 관리: 

연결 리스트는 요소의 동적 크기 관리에 매우 유용합니다. 

배열과 달리 연결 리스트는 요소를 추가하거나 제거할 때 메모리를 

효과적으로 확장하거나 축소할 수 있으며 메모리 관리에 대한 부담이 적습니다. 

예를 들어, 동적으로 크기가 조절되는 스택 또는 큐를 구현할 때 사용할 수 있습니다.

데이터 삽입 및 삭제: 

연결 리스트는 데이터 요소를 중간에 삽입하거나 삭제하는 작업이 배열보다 효율적입니다. 

예를 들어, 특정 위치에 요소를 삽입하거나 삭제해야 하는 상황에서 연결 리스트가 유용합니다.

메모리 효율성: 

연결 리스트는 메모리의 조각화를 방지할 수 있으며, 

메모리가 연속적으로 할당되는 배열에 비해 메모리를 더 효율적으로 활용할 수 있습니다.

그래프 및 트리 구조: 

그래프나 트리와 같은 비선형 자료 구조의 구현에 연결 리스트가 사용됩니다. 

트리의 각 노드가 자식 노드에 대한 연결을 가지는 구조와 같이 연결 리스트는 

재귀적인 데이터 구조를 표현하는 데 효과적입니다.

파일 시스템: 

파일 시스템에서 디렉토리의 구조를 나타내는데 연결 리스트가 사용될 수 있습니다. 

각 디렉토리가 그 내용을 가리키는 포인터로 연결되는 구조를 이용합니다.

브라우저 히스토리: 

웹 브라우저의 방문한 웹 페이지 히스토리를 저장하거나 뒤로가기 및 앞으로 가기 기능을 구현할 때 

연결 리스트를 사용할 수 있습니다. 

각 페이지가 다음과 이전 페이지를 가리키는 방식으로 구현됩니다.

메모리 캐시 관리: 

메모리 캐시에서 데이터를 저장하고 최신 데이터를 추적하거나 삭제하는 데 

연결 리스트가 사용될 수 있습니다.

이러한 상황에서 연결 리스트는 데이터 구조의 유연성과 효율성을 제공하며, 

데이터의 삽입, 삭제, 및 동적 크기 조절을 수행해야 할 때 특히 유용합니다.