1.선형 자료구조
- 데이터 요소가 순차적으로 배열되는 자료구조이다.
- 하나의 자료 뒤에 하나의 자료가 존재하여 자료들 간의 앞뒤 관계가 1:1인 구조이다.
- 배열, 연결 리스트, 스택, 큐, 해시가 선형 자료구조에 해당한다.
2. Array
정의
- 배열은 크기를 지정하고, 해당 크기 만큼의 연속된 메모리 공간을 할당 받는 자료구조이다.
특징
- 아래는 정수형으로 선언한 배열로 3개의 정수값을 가지고 있기 때문에 할당된 메모리도 12byte이다. (각 정수는 4byte를 차지하기 때문에 4byte * 3개 = 12byte)
- 또한 각 값마다 index(주소)를 가지고 있어서 조회할 때 즉시 index를 계산하여 찾을 수 있다.
동적 배열
- 하지만 실제데이터에서는 전체 크기를 예상하기 힘든 경우가 많기 때문에, 메모리를 너무 작게 할당하여 모자라거나 너무 많은 영역을 할당하여 낭비되는 경우가 생긴다.
- 따라서 크기를 지정하지 않고 배열의 크기에 따라 자동으로 리사이징이 가능한 동적 배열이 등장했다.
- 리사이징은 대게 더블링(할당된 용량을 2배씩 늘려줌)을 사용하지만 언어에 따라 늘려주는 비율은 조금씩 상이하다.
- Java에 경우는 1.5배, Python의 경우는 초반에는 2배씩 늘려 가지만, 전체적으로 약 1.125배씩 더블링을 해간다.
- 아래 배열을 보면 배열의 크기가 꽉 찬 다음에 추가로 데이터를 삽입하면 할당되는 용량이 늘어나는 것을 확인할 수 있다.
시간 복잡도
- 조회 할 때 : 지정된 인덱스를 찾으면 되기 때문에 O(1)
- 삽입 / 삭제할 때 : 삽입이나 삭제 후 인덱스를 다시 지정해줘야 하기 때문에 O(N)
- 따라서 배열은 데이터를 조회할 때 유리한 자료구조이다.
stack과 heap에서 배열이 할당되는 과정
- 실제 데이터는 heap 영역에 저장되지만 해당 데이터를 참조하는 참조값은 stack 영역에 저장된다.
- 배열(Array)을 heap 영역에 저장한 후 해당 배열을 참조하는 로컬변수 arr을 stack 영역에 저장한다.
- 배열의 데이터를 참조하는 참조값은 stack이 아닌 heap에 할당되어 배열 내의 index가 참조값이 되어 해당 데이터를 참조한다.
3. Linked List
정의
- 어떠한 노드가 데이터와 다음 노드에 대한 주소 정보(포인터)를 가지고 노드들끼리 순차적으로 연결되어있는 방식의 자료구조이다.
특징
- 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하다.
- 데이터가 반드시 연속적으로 저장되지 않아도 되기 때문에 관리하기가 쉽다.
- 데이터를 포인터로 연결하기 때문에 다양한 방법으로 활용이 가능하다.
종류
- 단일연결 리스트 : 노드와 다음 노드의 연결이 단방향으로 진행되는 리스트로 지금까지 살펴본 내용이 여기에 해당한다.
- 이중연결 리스트 : 노드와 다음 노드의 연결이 양방향으로 진행되는 리스트이다. 따라서 이전 노드 조회가 가능하여 단일연결 리스트보다 조회하는데는 이점을 보인다.
- 원형연결 리스트 : 마지막 노드의 포인터가 처음 노드를 가리키는 리스트이다. 단일연결 리스트와는 다르게 조회할 때 처음노드로 돌아갈 필요없이 연속적으로 탐색이 가능하다.
- 원형이중연결 리스트 : 노드와 다음 노드의 연결이 양방향으로 진행되는 것은 물론이고, 마지막 노드와 처음 노드도 양방향으로 연결되어 있는 리스트이다.
시간 복잡도
- 조회할 때 : 인덱스가 지정되어 있지 않기 때문에 특정 데이터에 접근하려면 리스트 전체를 순서대로 읽어야 하므로 O(N)이 소요된다.
- 삽입 / 삭제할 때 : 리스트는 보통 시작 또는 끝 지점에 데이터를 삽입하거나 삭제하는데 이 때는 0(1)이 소요된다.
- 따라서 연결 리스트는 데이터의 잦은 삽입이나 삭제가 일어날 때 유리한 자료구조이다.
4. 파이썬에서 리스트 주요 연산 시간 복잡도
Macro Developer