#. 연결 리스트
##1. 연결 리스트란?
연결 리스트는 데이터 요소들을 노드(Node)로 구성하고, 각 노드가 데이터와 다음 노드를 가리키는 링크(포인터)를 가지는 자료구조이다.
각 노드는 메모리에서 불연속적으로 할당되며, 링크(포인터)를 통해 서로 연결되어 있는 특징을 가지고 있다.
##2. 연결 리스트의 특징
-
연결 리스트는 데이터 요소들을 순차적으로 저장하지 않고, 각 노드가 링크를 통해 서로 연결되어 있기 때문에 데이터의 삽입과 삭제가 유연하게 이루어진다.
-
연결 리스트는 크기를 동적으로 조정할 수 있으며, 메모리 공간을 효율적으로 사용할 수 있다.
-
하지만 연결 리스트는 특정 위치의 데이터에 접근하기 위해서는 처음부터 순회해야 하므로, 탐색에는 선형 시간이 소요된다.
##3. 연결 리스트의 종류
###3.1 단일 연결 리스트(Singly Linked List)
각 노드는 데이터와 다음 노드를 가리키는 링크(포인터)로 구성되어 있다.
노드1(head) = data, next(노드2를 가리킴)
노드2 = data, next(노드3을 가리킴)
노드3(tail) = data, next(다음 노드가 없다면 null)
###3.2 이중 연결 리스트(Doubly Linked List)
각 노드는 데이터와 이전 노드를 가리키는 링크(포인터), 다음 노드를 가리키는 링크(포인터)로 구성되어 있다. 이중 연결 리스트는 양방향으로 탐색이 가능하므로 탐색의 효율성이 높아진다.
노드1(head) = data, prev(이전 노드가 없다면 null), next(노드2를 가리킴)
노드2 = data, prev(노드1을 가리킴), next(노드3을 가리킴)
노드3(tail) = data, prev(노드2을 가리킴), next(다음 노드가 없다면 null)
###3.3 원형 연결 리스트(Circular Linked List)
마지막 노드가 첫 번째 노드를 가리키는 링크(포인터)를 가지는 연결 리스트이다.
원형으로 연결되어 있기 때문에 마지막 노드에서 첫 번째 노드로 순회할 수 있다.
노드1(head) = data, next(노드2를 가리킴)
노드2 = data, next(노드3을 가리킴)
노드3(tail) = data, next(다음 노드가 없다면 노드1을 가리킴)
##4. 연결 리스트의 장점과 단점
###4.1 장점
- 데이터의 삽입과 삭제가 유연하게 이루어질 수 있다.
- 크기를 동적으로 조정할 수 있어 메모리 공간을 효율적으로 사용 가능하다.
###4.2 단점
- 특정 위치의 데이터에 접근하기 위해서는 처음부터 순회해야 하므로 탐색에는 선형 시간이 소요된다.
- 포인터의 추가적인 메모리 공간이 필요하다.
##5. 연결 리스트의 시간 복잡도
데이터의 삽입과 삭제: O(1)의 시간 복잡도를 가진다.
데이터의 탐색과 접근: O(n)의 시간 복잡도를 가진다. (단일 연결 리스트의 경우)
##6. 연결 리스트의 사용
###6.1 데이터의 동적 추가와 삭제
연결 리스트는 데이터의 삽입과 삭제가 유연하게 이루어질 수 있다.
데이터를 삽입하거나 삭제할 때, 해당 위치의 노드의 링크만 변경하면 되기 때문에 다른 요소들에 영향을 주지 않고 연결 리스트를 수정할 수 있다.
###6.2 파일 관리
파일 시스템에서는 파일들의 정보를 연결 리스트로 관리하기도 한다.
각 파일을 노드로 표현하고, 링크로 연결하여 파일들을 관리할 수 있다. 이를 통해 파일의 추가, 삭제, 탐색 등을 효율적으로 수행할 수 있다.
###6.3 큐(Queue)와 스택(Stack)의 구현
연결 리스트를 활용하여 큐와 스택을 구현할 수 있다.
큐의 경우, 데이터를 연결 리스트의 끝에 추가하고, 삭제는 맨 앞에서 진행한다.
스택의 경우, 데이터를 연결 리스트의 맨 앞에 추가하고, 삭제도 맨 앞에서 진행한다.
###6.4 문자열 처리
연결 리스트는 문자열 처리에 유용하게 사용될 수 있다.
문자열을 문자 단위로 분리하여 각 문자를 노드로 표현하고, 링크로 연결하여 문자열을 저장하거나 조작할 수 있다. 이를 통해 문자열의 삽입, 삭제, 역순 등 다양한 연산을 수행할 수 있다.
