자료구조 : Linked List

오늘은

프로젝트에서 사용하기 위해 자료구조를 공부하며 링크드리스트에 대해 공부한 내용을 

간단히 적어보겠습니다. 

 

링크드 리스트(Linked List)는 데이터 구조의 한 유형으로, 각 요소(노드)가 데이터와 다음 요소를 가리키는 포인터를 포함하는 방식으로 구성됩니다. 이는 배열과 달리 요소들이 물리적으로 연속되어 있지 않으며, 논리적으로 연결된 구조를 갖습니다. 링크드 리스트는 데이터의 동적 할당 및 삽입, 삭제가 빈번히 일어나는 상황에서 유용합니다.

 

1. 링크드 리스트의 구성 요소

1.1. 노드(Node): 링크드 리스트의 기본 구성 요소. 각 노드는 다음과 같은 두 부분으로 이루어져 있습니다.
   - 데이터(Data): 노드가 저장하는 값
   - 포인터(Next): 다음 노드를 가리키는 참조(주소)
1.2. 헤드(Head): 리스트의 첫 번째 노드를 가리키는 포인터입니다. 리스트의 시작점을 나타냅니다.
1.3. 테일(Tail): 리스트의 마지막 노드로, 이 노드의 다음 포인터는 NULL을 가리킵니다.

2. 링크드 리스트의 유형

2.1. 단일 링크드 리스트(Singly Linked List): 각 노드는 오직 다음 노드를 가리키는 하나의 포인터를 가집니다.

2.2. 이중 링크드 리스트(Doubly Linked List): 각 노드는 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 가집니다.

2.3. 원형 링크드 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리켜 리스트가 원형으로 연결됩니다.

3. 링크드 리스트의 장점과 단점

장점:
- 동적 크기: 배열과 달리 링크드 리스트는 동적으로 크기를 조절할 수 있습니다.
- 효율적인 삽입/삭제: 노드의 삽입과 삭제가 리스트의 중간에서 효율적으로 이루어질 수 있습니다.

단점:
- 추가 메모리 사용: 각 노드가 데이터 외에 포인터를 저장해야 하므로 추가적인 메모리 공간이 필요합니다.
- 느린 접근 속도: 특정 위치의 노드를 접근하기 위해 처음부터 순차적으로 접근해야 하므로 시간이 더 걸립니다. (Full Scan)