지금부터 다룰 자료 구조는 모두 '노드(node)'라는 개념에 기반해 만들어졌다.
노드란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하기 때문에 성능상 이점이 많다.
'연결 리스트'는 가장 기본적인 노드 기반 자료 구조이다. 배열과 거의 같아 보이지만, 연결 리스트는 효율성 면에서 장단점이 있다.
13. 1 연결 리스트
연결 리스트(linked list)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 배열과 연결 리스트는 외견상 상당히 비슷해 보이지만, 내부적으로는 크게 다르다.
컴퓨터 메모리는 데이터 조각을 저장하는 셀들의 거대한 집합이다. 따라서 배열을 생성하면 메모리 내에 연속된 빈 셀 그룹을 찾아 데이터를 저장할 수 있도록 할당한다.
컴퓨터는 어떤 메모리 주소든 한 번에 접근할 수 있다. 그래서 배열 내 어떤 인덱스든 바로 갈 수 있다는 점을 배웠었다. 다시 말하지만 프로그램은 배열이 어떤 메모리 주소부터 시작하는지, 가령 메모리 주소 1000인지 알고 있으며, 인덱스 4를 찾고 싶으면 간단히 메모리 주소 1004로 가면 된다는 것을 알고 있다.
반면, 연결 리스트는 상당히 다르게 동작한다. 연결 리스트 내 데이터는 연속된 메모리 블록이 아니라, 컴퓨터 메모리 전체에 걸쳐 여러 셀에 펴져 있을 수 있다. 그리고 메모리 곳곳에 흩어져 연결된 데이터를 노드(node)라 부른다.
노드가 메모리 내에 서로 인접해 있지 않는데 어떤 노드들이 같은 연결 리스트에 속하는지 아는 방법이 바로 연결 리스트의 핵심이다. 각 노드는 약간의 추가 정보, 즉 연결 리스트 내에 다음 노드의 메모리 주소를 포함한다..!
다음 노드의 메모리 주소로의 포인터를 '링크(link)'라 부른다.
위 예제에선 연결 리스트에 "a", "b", "c", "d" 총 4개의 데이터가 있다. 하지만 데이터를 저장하는 데 각 노드마다 메모리 셀 두 개씩, 총 메모리 셀 8개를 사용한다. 첫 번째 셀에는 실제 데이터가 들어 있고, 두 번째 셀에는 다음 노드의 시작 메모리 주소를 뜻하는 링크가 들어 있다. 마지막 노드의 링크는 연결 리스트가 끝나므로 null이다.
(연결 리스트의 첫 번째 노드를 헤드(head), 마지막 노드를 테일(tail)이라고도 부른다)
컴퓨터가 연결 리스트의 시작 메모리 주소를 알면 그 리스트를 다룰 수 있다. 각 노드에 다음 노드의 링크가 들어 있으니 각 링크를 따라 전체 리스트를 연결하기만 하면 된다.
데이터가 컴퓨터 메모리 전체에 흩어질 수 있다는 점에서 연결 리스트가 배열보다 유리할 수 있다. 배열은 데이터를 저장하기 위해 연속된 전체 셀 블록을 찾아야 하는데 배열이 커질수록 굉장히 어렵기 때문이다.
13. 2 읽기
컴퓨터는 배열에서 O(1) 만에 값을 읽는다. 그렇다면 연결 리스트에서 읽기의 효율성은 어떤가?
가령 연결 리스트의 세 번째 항목에 있는 값을 읽을 때, 컴퓨터는 메모리 어디에서 찾아야 할지 바로 알 수 없으므로 한 단계로 찾을 수 없다. 프로그램은 연결 리스트의 첫 번째 노드의 메모리 주소만 알고, 나머지 노드가 어디에 있는지 바로 알지 못한다.
따라서 세 번째 노드를 읽으려면 일련의 과정을 거쳐야 한다.
먼저 첫 번째 노드에 접근한다. 이어서 첫 번째 노드의 링크를 따라 두 번째 노드로 가고 뒤이어 두 번째 노드의 링크를 따라 세 번째 노드로 간다. 어떤 노드를 가든 항상 첫 번째 노드부터 시작해야 하고, 원하는 노드에 도달할 때까지 노드 사슬을 따라가야 한다.
리스트의 마지막 노드를 읽으려면 리스트에 노드가 N개일 때 N단계가 걸린다. 연결 리스트 읽기에서 최악의 시나리오가 O(N)이라는 점은 O(1)만에 읽는 배열에 비해 심각한 단점이다.
13. 3 검색
검색은 리스트 내에서 값을 찾아 그 인덱스를 반환하는 것이다. 배열을 선형 검색할 때 컴퓨터는 한 번에 한 값씩 검사하므로 속도가 O(N)이었다.
연결 리스트의 검색 속도도 O(N)이다. 값을 검색하려면 읽기와 비슷한 과정을 거쳐야 한다. 즉 첫 번째 노드에서 시작해 각 노드의 링크를 따라 다음 노드로 간다. 그리고 찾는 값이 나올 때까지 매 값을 검사한다.
13. 4 삽입
연결 리스트가 배열에 비해 뚜렷한 장점을 보이는 연산이 바로 '삽입'이다.
배열 삽입에서 최악의 시나리오는 프로그램이 인덱스 0에 데이터를 삽입할 때였다. 나머지 데이터를 한 셀씩 오른쪽으로 옮겨야 하므로 효율성이 O(N)이었다.
반면 연결 리스트는 리스트 앞에 삽입하는 데 딱 한 단계, O(1)만 걸린다.
만약 다음과 같은 연결 리스트가 있다고 하자.
"yellow"를 리스트 앞에 삽입하려면 그냥 새 노드를 생성하고, 그 노드가 "blue"를 포함하는 노드를 가리키게끔 하면 된다.
배열과 달리 연결 리스트에는 데이터를 하나도 움직이지 않고 리스트 앞에 데이터를 삽입할 수 있는 장점이 있다. 이론적으로 데이터를 연결 리스트 내 어디에 삽입하든 딱 한 단계만 걸린다. 하지만 주의사항도 있다.
"purple"을 인덱스 2("blue"와 "green" 사이)에 삽입해보자. 실제 삽입은 한 단계면 된다. 그러나 컴퓨터가 이렇게 수행하려면 먼저 인덱스 1에 있는 노드("blue")로 가야지 그 노드의 링크가 새로 생성된 노드를 가리키도록 수정할 수 있다. 앞서 봤듯이 주어진 인덱스의 항목에 접근하는 연결 리스트 읽기는 이미 O(N)이 걸린다.
새 노드를 인덱스 1 뒤에 추가하고 싶다면, 컴퓨터는 리스트의 인덱스 1로 가야 한다. 그렇게 하기 위해 리스트 앞에서부터 시작해야 한다.
인덱스 0부터 시작해서 링크를 따라 다음 노드에 접근한다.
인덱스 1을 찾았으므로 이제 새 노드를 추가한다.
이때 "purple"을 추가하는 데 3단계가 걸렸다. 리스트 끝에 추가했다면 더 많은 단계가 소요됐을 것이다.
결국 리스트 끝에 삽입하는 최악의 시나리오에 N + 1단계가 걸리니 사실상 연결 리스트 삽입은 O(N)이다.
하지만, 리스트 앞에 삽입하는 최선의 시나리오에는 O(1)이다.
흥미롭게도 배열과 연결 리스트의 최선, 최악의 시나리오는 정 반대다.
배열은 끝에 삽입할 때, 연결 리스트는 앞에 삽입할 때 유리하다.
13. 5 삭제
연결 리스트는 삭제도 매우 빠르다. 특히 리스트 앞에서 삭제할 때 그렇다.
연결 리스트 앞에서 노드를 삭제하려면 한 단계면 된다. 단순히 두 번째 노드부터 시작하도록 연결 리스트를 바꾸면 된다. 반대로 배열은 첫 번째 원소를 삭제할 때 나머지 데이터를 모두 한 셀씩 왼쪽으로 시프트해야 하므로 효율성이 O(N)이다.
연결 리스트에서 마지막 노드를 삭제할 경우, 실제 삭제에는 한 단계가 걸리는데 끝에서 두 번째 노드를 가져와 링크를 null로 만들기 위해 리스트 앞에서부터 시작해서 노드에 도착할 때까지 링크를 따라가야 하므로 이미 N단계가 걸린다. 그래서 삽입과 동일한 최선, 최악의 시나리오를 가진다.
중간에서의 삭제는 삭제하려면 노드의 바로 앞 노드에 접근해야 한다. 이어서 그 링크가 삭제하려는 노드 바로 뒤 노드를 가리키도록 바꾼다.
13. 6 연결 리스트 연산의 효율성
전체적으로 보면 시간 복잡도 면에서 연결 리스트는 그다지 매력적이지 않다. 검색과 삽입, 삭제는 배열과 비슷하고, 읽기는 훨씬 느리다.
연결 리스트가 효과적으로 쓰이려면 실제 삽입과 삭제 단계가 O(1)이라는 점을 활용해야 한다. 맨 앞에서 삽입과 삭제하는 경우가 아니라면 해당 노드에 접근하는 데만 최대 N단계가 걸리는 한계를 극복해야 한다.
13. 7 연결 리스트 다루기
연결 리스트가 빛을 발하는 경우는, 한 리스트를 검사해서 많은 원소를 삭제할 때다.
예를 들어 이메일 주소 리스트를 검토해서 유효하지 않은 형식의 이메일을 모두 삭제하는 프로그램을 만든다고 생각해보자.
리스트가 배열이든 연결 리스트든 전체 리스트를 한 번에 한 원소씩 살펴보며 각 값을 검사해야 하므로 N단계가 걸린다. 하지만 배열에서는 이메일 주소를 삭제할 때마다 빈 공간을 메꾸기 위해 나머지 데이터를 왼쪽으로 시프트해야 하는 또 다른 O(N) 단계가 필요하다. 하나의 메일을 지울 때마다 해당 행위는 발생한다.
이메일 주소 열 개 중 하나가 유효하지 않다면, 이메일 주소 천 개로 이뤄진 리스트엔 약 100개가 유효하지 않을 것이다. 알고리즘이 이메일 천 개를 모두 읽는 데 1,000단계가 걸린다. 더불어 유효하지 않은 주소 100개를 삭제할 때 다른 원소 천 개를 시프트해야 할 수 있으니 삭제에 추가로 약 100,000단계가 걸린다.
그러나 연결 리스트에서는 리스트 전체를 살펴보면서 삭제가 필요하면 그저 그 노드의 링크가 적절한 노드를 가리키도록 바꾸면 되므로 각 삭제마다 딱 한 단계가 걸린다. 이메일 천 개가 있을 때, 알고리즘은 1,000개의 읽기 단계와 100개의 삭제 단계, 딱 1,100단계만 걸린다.
연결 리스트는 삽입이나 삭제 시 다른 데이터를 시프트하지 않아도 되므로 전체 리스트를 훑으며 삽입이나 삭제를 수행하기에 매우 알맞은 자료 구조다.
13. 8 이중 연결 리스트
연결 리스트는 다양한 변형이 있다. 그중 하나가 '이중 연결 리스트(doubly linked list)'다.
이중 연결 리스트는 각 노드에 2개의 링크가 있다는 점만 제외하면 '전형적인' 연결 리스트와 비슷하다. 한 링크는 다음 노드를 가리키고, 다른 한 링크는 앞 노드를 가리킨다. 또한 첫 번째 노드 외에 마지막 노드도 항상 기록한다.
이중 연결 리스트는 항상 첫 노드와 마지막 노드를 모두 알고 있으므로 각각 한 단계, 즉 O(1)에 접근할 수 있다. 따라서 '리스트 앞'에서의 읽기나 삽입, 삭제를 O(1)에 하듯이 '리스트 끝'에서도 O(1)에 할 수 있다.
새로운 노드("Sue")를 생성해서 이 노드의 이전 링크가 원래 마지막 노드("Greg")를 가리키도록 하고, 반대로 "Greg" 노드의 다음 링크가 "Sue" 노드를 가리키도록 바꾼다. 끝으로 새 노드("Sue")를 이 연결 리스트의 마지막 노드로 선언하면 끝난다.
"전형적인" 연결 리스트는 앞으로만 이동할 수 있다. 즉 첫 번째 노드에 접근해 링크를 따라 리스트의 나머지 노드를 찾을 수 있다. 하지만 이전 노드를 몰라 뒤로는 이동할 수 없다.
반면, "이중 연결 리스트"는 리스트 앞과 뒤로 모두 이동할 수 있어 훨씬 유연하다.
13. 9 이중 연결 리스트 기반 큐
이중 연결 리스트는 리스트 앞과 끝 모두에 바로 접근할 수 있다.
그래서 O(1) 시간에 리스트 앞에서 데이터를 삭제할 수 있고, 리스트 뒤에 데이터를 삽입할 수 있으므로 '큐를 위한 완벽한 내부 자료 구조'로 쓰인다.
큐는 데이터를 끝에만 삽입할 수 있고 앞에서만 삭제할 수 있는 항목들의 리스트이다. 큐가 추상 데이터 타입의 하나로써 끝에서 삽입하고 앞에서 삭제하므로 내부 자료 구조로서 배열이 잘 어울린다. 그러나 배열은 끝에 삽입하는 데 O(1)이지만 앞에서 삭제하는 데 O(N)인 한계를 가진다.
반면 이중 연결 리스트는 끝에서 삽입하고 앞에서 삭제하는 데 모두 O(1)이다. 따라서 큐의 내부 자료 구조로서 완벽하다.
13.10 마무리
연결 리스트를 알아보며 노드 개념을 배웠다. 그러나 연결 리스트는 가장 단순한 노드 기반 자료 구조일 뿐이다. 앞으로는 보다 복잡하면서 흥미로운 노드 기반 구조를 배운다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| Ch.15 힙으로 우선순위 유지하기 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.11 |
|---|---|
| Ch.14 이진 탐색 트리로 속도 향상 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.10 |
| Ch.12 속도를 높이는 재귀 알고리즘 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
| Ch.11 재귀적으로 작성하는 법 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.07 |
| Ch.10 재귀를 사용한 재귀적 반복 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.06 |
