[데이터 구조] 연결 리스트(Linked lists)

연결 리스트란?

연결 리스트(Linked Lists)는 데이터의 집합을 저장하기 위해 사용되는 데이터 구조이며, 아래와 같은 속성을 갖는다.

• 연속되는 항목들이 포인터로 연결된다.
• 마지막 항목은 NULL을 포인트 한다.
• 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.
• 시스템 메모리가 허용하는 한 필요한 만큼 길어질 수 있다.
• 메모리 공간을 낭비하지 않는다.
   (하지만, 포인터를 위한 추가의 메모리를 필요로 한다.)

연결 리스트 ADT

다음의 연산 연결 리스트를 추상 데이터형,
즉, ADT(Abstract Data Type)가 되도록 한다.

연결 리스트의 주요 연산들

• 삽입: 항목을 리스트에 추가한다.
• 삭제: 지정된 위치의 항목을 리스트로부터 삭제하며 리턴한다.

연결 리스트의 보조적 연산들

• 리스트 삭제: 리스트의 모든 항목을 삭제한다.(리스트도 삭제)
• 개수 세기: 리스트의 항목의 개수를 리턴한다.
• 리스트의 끝으로부터 n번째 항목 찾기 등

왜 연결 리스트를 사용하는가?

연결 리스트와 같은 기능을 하는 많은 다른 데이터 구조들이 있다.

연결 리스트에 대하여 논의하기 전에 연결 리스트와 배열의 차이점을 이해하는 것이 중요하다.

연결 리스트와 배열 모두 데이터 집합을 저장하기 위해 사용된다.

이 둘이 같은 목적으로 사용되므로 둘의 용도를 구분해야 할 필요가 있다.

즉, 어떤 경우에 배열이 적합하고 어떤 경우에 연결 리스트가 적합한가 하는 것이다.

배열 개요

배열의 항목을 저장하기 위해 메모리 블록 하나가 할당된다.

배열의 항목은 특정 항목의 인덱스를 첨자로 사용하여 일정한 시간으로 접근할 수 있다.

배열의 항목에 접근하는데 왜 일정한 시간이 걸리는가?

배열의 항목에 접근하기 위해서는 항목의 주소가 배열의 기본 주소로부터의 오프셋으로 계산되고 한 번의 곱셈 연산으로 항목의 주소를 구하기 위해 기본 주소에 더해져야 할 값이 계산된다.

처음에 데이터형에 따른 항목의 크기가 계산되고, 그것이 항목의 인덱스에 곱해져서 기본 주소에 더해질 값이 된다.

이 과정에서 한 번의 곱셈과 한 번의 덧셈이 필요하다.

이 두 연 산이 일정한 시간이 걸리므로 배열 접근은 일정한 시간으로 수행된다고 할 수 있다.

배열의 장점

• 간단하고 사용하기 쉽다.
• 항목에서의 접근이 더 빠르다.(일정한 시간이 걸리는 접근)
• 메모리 안에서의 특수한 지역성
• 연속된 메모리 블록으로 정의되므로 배열의 항목들은 물리적으로 근처에 위치한다.
   이것은 현대의 CPU 캐싱 기법에 매우 유리하다.

배열의 단점

• 고정된 크기: 사용하기 전에 배열의 크기를 지정해줘야 하기 때문에 배열의 크기는 정적이다.
• 한 블록의 할당: 배열 크기가 클 경우 처음 배열을 할당할 때 전체 배열을 위한 메모리를 얻지 못할 때도 있다.
• 복잡한 위치 기반의 삽입: 주어진 위치에 항목을 삽입하려면 새 항목 추가할 자리 마련을 위해 기존의 항목들을 이동해야 할 수 있다.
   만약 새 항목을 추가할 자리가 가장 앞이면 다른 항목들의 이동 연산이 더욱 오래 걸리게 된다.

동적 배열

동적 배열(또는 확장 가능 배열, 크기 변경 가능 배열, 동적 테이블, 배열 리스트 등으로 불린다)은 랜덤 접근하는 크기가 변하는 리스트 데이터 구조로 새로운 항목들이 추가되거나 삭제될 수 있다.

동적 배열을 구현하는 한 가지 간단한 방법은 처음에 일정한 고정된 크기의 배열로 시작하는 것이다.

이 배열이 가득 차면, 원래 배열의 두 배 크기의 새 배열을 만든다.

마찬가지로, 배열의 항목의 수가 절반 이하가 되면 배열 크기를 반으로 줄인다.

연결 리스트의 장점

• 일정한 시간으로 확장 가능하다.
• 하나의 항목을 위한 공간으로 시작해서 복사나 재할당 없이 새 항목을 쉽게 추가할 수 있다.

연결 리스트의 단점

• 개별 항목에 접근하는 접근 시간이 길다.
• 배열은 랜덤 접근이 가능하므로 배열의 항목에 접근하는데 O(1)의 시간이 걸린다.
   연결 리스트는 리스트의 항목에 접근하는데 최악의 경우 O(n)의 시간이 걸린다.
• 저장 공간의 동적 할당이 큰 장점이긴 하지만 데이터의 저장과 인출에 더해지는 부담이 큰 차이를 만든다.
• 마지막 항목이 삭제되면, 가장 끝에서 하나 전의 항목을 찾아 그 포인터가 NULL을 가리키게 하기 위해 리스트가 탐색되어야 한다.
• 연결 리스트에서는 추가적인 참조 포인터를 위한 메모리 공간이 낭비된다.

연결 리스트와 배열 그리고 동적 배열의 비교

참고

다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java