연결 리스트(Linked List)

연결 리스트 (Linked List)

https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

 

연결 리스트는 노드의 집합으로, 각 노드가 다음 노드를 가리키는 포인터를 통해 순차적으로 연결된 구조이다.

연결 리스트는 동적 메모리 할당을 사용해 구현되며, 배열과 달리 런타임에 크기가 변경될 수 있다.

연결 리스트의 각 요소는 데이터 필드와 하나 혹은 그 이상의 다음(next) 링크 필드로 구성된다. 즉, 비엔나 소세지 마냥 줄줄이 이어져 있는 느낌이다.

 

연결 리스트의 종류

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

https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

• 각 노드가 다음 노드만을 가리키는 포인터를 가지며 리스트의 첫 번째 노드는 헤드(Head)라고 한다.
• 리스트의 마지막 노드는 꼬리(Tail)이며 다음 노드가 없음을 나타내는 NULL 값을 가진다.

작동 원리

• 삽입(Insertion)
  • 새로운 노드를 추가할 때는, 새 노드의 다음 포인터를 이전 노드가 가리키던 노드로 설정하고, 이전 노드의 다음 포인터를 새 노드로 변경한다.
  • 헤드에 노드를 삽입하는 경우, 새 노드는 현재 헤드를 가리키고, 새 노드가 새로운 헤드가 된다.
• 삭제(Deletion)
  • 노드를 삭제하려면, 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키도록 포인터를 변경한다.
  • 헤드 노드를 삭제할 경우, 현재 헤드의 다음 노드가 새로운 헤드가 된다.
• 검색(Searching)
  • 특정 데이터를 찾기 위해선 헤드부터 시작하며, 각 노드를 순차적으로 탐색해야 한다.

 

장단점

• 장점
  • 동적 메모리 관리 : 필요에 따라 노드를 추가하거나 삭제할 수 있어, 메모리를 효율적으로 사용할 수 있다.
  • 삽입과 삭제가 용이 : 배열에 비해 특정 위치에 데이터를 삽입하거나 삭제하는 과정이 이전 노드의 포인터만 조정하면 되기 때문에 간단하다.
• 단점
  • 임의 접근 불가 : 특정 요소에 접근하기 위해선 처음부터 순차적으로 탐색해야 하기 때문에, 배열처럼 인덱스를 이용한 직접 접근이 불가능하다.
  • 추가적인 메모리 공간 필요 : 각 노드가 데이터와 다음 노드를 가리키는 포인터를 모두 저장해야 하므로, 추가적인 메모리 공간이 필요하다.

 

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

https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

• 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터(참조)를 가지고 있는 구조이다.
• 이러한 구조 덕분에, 이중 연결 리스트는 양방향으로의 탐색이 가능하며, 단일 연결 리스트에 비해 더 유연한 작업 수행이 가능하다.

작동 원리

• 삽입(Insertion)
  • 새로운 노드를 추가할 때, 새 노드의 이전 포인터는 이전 노드를 가리키고, 다음 포인터는 이전 노드가 가리키던 다음 노드를 가리킨다.
  • 그리고 이전 노드의 다음 포인터와 다음 노드의 이전 포인터는 새 노드를 가리키게 조정된다. 이 과정을 통해 리슽 중간에 쉽게 삽입할 수 있다.
• 삭제(Deletion)
  • 노드를 삭제할 때, 삭제할 노드의 이전 노드의 다음 포인터를 삭제할 노드의 다음 노드로, 그리고 삭제할 노드의 다음 노드의 이전 포인터를 삭제할 노드의 이전 노드로 조정하여 연결을 끊는다.
• 검색(Searching)
  • 이중 연결 리스트에서는 양방향으로 탐색이 가능하기 때문에, 시작점이 헤드 노드일 수도 있고, 테일 노드일 수도 있어 특정 조건에 따라 탐색의 방향을 결정할 수 있다.

 

장단점

• 장점
  • 양방향 탐색 : 이전 노드와 다음 노드를 가리키는 포인터 덕분에 앞 뒤로 자유롭게 탐색할 수 있어, 특정 상황에서의 탐색 효율이 좋습니다.
  • 삽입과 삭제의 유연성 : 중간에 노드를 삽입하거나 삭제하는 경우, 이전 노드와 다음 노드의 포인터만 조정하면 되므로 상대적으로 간단하고 빠르다.
  • 양 끝에서의 작업 용이 : 헤드와 테일 노드가 있어 양쪽 끝에서의 추가, 삭제 작업이 편리하다.
• 단점
  • 메모리 사용 증가 : 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 사용하기 때문에, 각 노드당 추가적인 메모리가 필요하다. 
  • 구현 복잡성 : 삽입이나 삭제 시, 두 포인터를 모두 정확히 관리해야 하므로 구현이 단일 연결 리스트에 비해 복잡하다.

 

순환 연결 리스트 (Circular linked list)

https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

• 마지막 노드가 첫 번째 노드를 가리키는 구조를 가지며, 이 구조는 단일 연결 리스트와 이중 연결 리스트 모두에 적용될 수 있다.
• 순환 연결 리스트의 핵심은 리스트의 마지막 노드가 다시 첫 번째 노드를 가리킨다는 점이다. 이로 인해 리스트를 순환하며 탐색할 수 있다.

 

작동 원리

• 삽입(Insertion)
  • 새 노드를 추가할 때, 기존 노드 사이에 위치시키거나 리스트의 시작 또는 끝에 추가할 수 있다.
  • 마지막 노드의 다음 포인터 또는 다음과 이전 포인터를 적절히 조정해 순환 구조를 유지한다.
• 삭제(Deletion)
  • 특정 노드를 삭제할 때, 해당 노드의 이전 노드와 다음 노드를 연결하여 순환 구조가 유지되도록 한다.
  • 삭제할 노드가 첫 번째 노드인 경우, 새로운 첫 번째 노드를 올바르게 설정해야 한다.
• 검색(Searching)
  • 특정 값을 가진 노드를 찾기 위해, 첫 번째 노드부터 시작하여 순환하며 각 노드를 확인한다.
  • 순환 리스트는 끝이 없기 때문에, 탐색 시작점으로 돌아오면 탐색을 중단한다.

 

장단점

• 장점
  • 순환 탐색 용이 : 시작점에서 리스트 전체를 순환할 수 있어, 어디서든 리스트 전체에 접근하기 쉽다.
  • 리스트의 시작과 끝 용이 : 마지막 노드가 첫 번째 노드를 가리키므로, 시작과 끝을 변경하는 것이 다른 연결 리스트에 비해 유연하다.
  • 큐 , 스택의 구현에 유용 : 순환 구조는 링 버퍼와 같은 데이터 구조의 구현에 유용하게 사용될 수 있다.
• 단점
  • 종료 조건 관리 필요 : 순환 구조이기 때문에, 탐색이나 다른 작업을 할 때 종료 조건을 명확히 설정해야 한다. 그렇지 않으면 무한 루프에 빠질 위험이 있다.
  • 구현 복잡성 : 삽입이나 삭제 시, 순환 구조를 올바르게 유지하기 위한 추가적인 로직이 필요할 수 있어 구현이 복잡해질 수 있다.