자료구조 - 리스트
1. 리스트란?
일렬로 나열된, 순서가 있고 데이터의 중복이 허용되는 자료 구조.
2. 리스트의 종류
2.1 배열(Array)
메모리상에서 연속적으로 저장하는 구조. 각 데이터마다 인덱스를 갖고 있어 이 인덱스를 사용해 특정 정보에 빠르게 접근할 수 있다.
2.1.1 배열의 종류
정적 배열(Array)
크기가 고정적인 배열.
동적 배열(Dynamic Array)
고정 배열의 한계를 극복하기 위해 설계된 데이터 구조로, 크기가 변경될 수 있다.
동적배열의 원리는,
초기 할당 일정 크기의 배열로 생성
요소 추가 및 자동 확장
배열에 요소를 추가할 때, 현재 배열의 크기가 충분한지 확인한다. 더이상 공간이 없다면 배열을 더 큰 크기로 확장하는데, 일반적으로 현재 크기의 2배(또는 고정 증가율)로 새로운 배열을 할당한다. 이를 배열 확장 또는 재할당이라고 한다.
배열이 확장되면, 기존 배열의 모든 요소를 새 배열로 복사한다. 이후 이 새 배열이 사용된다.
요소 제거 및 크기 조정
요소를 제거하는 경우에도 새로운 작은 배열을 할당하고 기존 요소들을 새 배열로 복사하는 식.
동적 배열의 확장 및 축소과정에서 요소들을 새 배열로 복사하는 작업은 O(n) 시간이 소요되지만 이런 일은 잘 발생하지 않으므로, 동적 배열의 평균적인 삽입시간 복잡도는 O(1)에 가깝다. 이를 암모타이즈드 상수 시간(Amortized Constant Time) 복잡도라고 한다. 평균적인 실행시간이 상수에 가깝다는 의미.
파이썬의 리스트가 이것에 해당된다.
2.1.2 배열의 연산
조회 O(1)
배열에서 특정 인데스의 요소에 접근하는 시간 복잡도는 상수시간이다. 이유는 단순하다. 배열의 각 요소는 연속적인 메모리 위치에 저장되므로, 인덱스를 알고 있다면 단 한 번의 연산으로 해당 요소에 접근할 수 있다.
수정 O(1)
조회와 마찬가지로, 수정하는 시간도 단 한 번의 연산으로 가능하다.
삽입
배열의 맨 끝에 요소 추가 O(1) 배열의 크기가 최대치에 도달해서 더 큰 배열로 재할당해야하는 경우(동적 배열) O(n)의 시간이 걸릴 수 있다. 하지만 드문 경우이기 때문에 평균적인 시간 복잡도는 O(1)에 가깝다.
배열의 특정 위치에 요소 추가 O(n) 배열의 중간에 요소를 삽입하는 경우, 삽입 위치 이후의 모든 요소를 한 칸 씩 이동시켜야한다. 최악의 경우는 모두 이동시켜야하므로 시간복잡도는 O(n)이 된다.
삭제
- 배열의 맨 끝에서 요소 삭제 O(1)
배열의 특정 위치에서 요소 삭제 O(n)
삭제된 요소 이후의 모든 요소를 한 칸 씩 앞으로 이동 시켜야 하므로, 최악의 경우 모든 요소를 이동시켜야한다.
2.2 연결 리스트(Linked List)
노드(Node)라고 불리는 요소들이 포인터를 통해 연결되어 있는 구조. 각 노드는 값을 가진 데이터 필드와, 다음 노드를 가리키는 포인터 필드로 구성된다.
2.2.1 연결 리스트의 종류
단일 연결 리스트(Singly Linkded List)
각 노드가 다음 노드만을 가리키는 연결 리스트.
이중 연결 리스트(Doubly Linkded List)
각 노드가 이전 노드와 다음 노드 양쪽을 가리키는 포인터를 가진 리스트. 양방향으로 순회 가능하다.
순환 연결 리스트(Circular Linkded List)
추가적으로, 연결 리스트를 이용해 순환적인 구조를 만들 수 있다. 이를 순환 연결 리스트(Circular Linkded List)라고 하는데, 마지막 노드가 다시 첫 번째 노드를 가리키는 구조이다.
2.2.2 연결 리스트의 연산
조회 O(n)
연결 리스트의 경우, 특정 요소를 조회하기 위해선 시작점부터 순차적으로 탐색해야한다. 최악의 경우는 모든 노드를 탐색해야하는 것.
수정 O(n)
수정하고자 하는 노드를 찾기 위해 순차적으로 탐색해야하므로, O(n)의 시간복잡도를 가진다. 하지만 노드를 찾고 나면 데이터를 수정하는 것 자체는 O(1)의 복잡도를 가진다.
삽입
리스트의 시작 또는 끝에 요소 삽입 O(1)
리스트의 시작에 삽입하는 경우, 새 노드를 생성하고 기존의 첫번째 노드를 가리키게 하면 된다. 리스트의 끝에 삽입하는 경우도 마지막 노드의 포인터를 새 노드로 변경하면 된다. 단, 이 경우는 이중연결리스트의 경우고 단일 연결 리스트에서는 마지막 노드를 찾기 위해 O(n)이다.
리스트의 중간에 요소 삽입 O(n)
특정 위치에 삽입하기 위해서는 해당 위치의 바로 앞 노드를 찾아야한다. 그래서 O(n). 하지만 삽입 위치를 알고 있다면 삽입 자체는 O(1)의 작업이다.
삭제
리스트의 시작 또는 끝에서 요소 삭제O(1)
시작 노드를 삭제하는 것은, 첫번 째 노드의 포인터를 두 번째 노드로 변경하면 된다. 이중 연결 리스트에서는 마지막 노드의 삭제도 O(1)이지만, 단일 연결 리스트의 경우에는 바로 앞 노드를 찾아야하므로 O(n)이다.
리스트의 중간에서 요소 삭제 O(n) 삽입의 경우와 동일하다. 특정 위치의 노드를 삭제하기 위해선 그 앞 노드를 찾아야하며, 이를 위해 순차적 탐색이 필요하기 때문에 O(n)이다.
3. 종합
배열은 인덱스를 통해 빠른 데이터 접근이 가능하지만, 중간에 요소를 삽입하거나 삭제할 때는 비효율 적이다.
연결 리스트는 노드의 삽입과 삭제가 다른 노드들에 미치는 영향이 적다. 하지만 특정 요소에 접근하거나 특정 위치를 찾기 위해서는 순차적으로 탐색해야하기 때문에 조회나 중간 요소의 수정, 삽입, 삭제는 비효율적이다.
4. 파이썬과 배열
파이썬에서의 List는 동적 배열로 이루어져 있다. 그리고 특징적이게도, 다양한 데이터 타입을 동일한 List에 삽입할 수 있다. 이것은 파이썬의 모든 것이 객체이고, List가 객체에 대한 참조를 저장하기 때문이다. 즉, 파이썬의 List에는 실제 데이터가 아닌 데이터 객체의 참조 주소가 저장된다.