1. 배열
1) 가장 기본적인 순차적 자료구조.
2) 인덱스(index) : 배열의 각 특정 위치에 있는 값을 나타내는 상수로 맨 처음 값의 index는 '0'으로 시작하여 1씩 증가.
3) 특징
- 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 형태로 구성된 자료구조
- 메모리 낭비. 인덱스에 따라 값을 유지해서 중간의 데이터가 삭제되어도 빈자리가 남게 된다.
- 배열의 크기가 유동적이지 못하다. 처음 지정한 크기보다 적은 데이터가 들어있어도 배열의 크기에는 변동이 없으며, 반대로 처음에 지정한 크기보다 많은 데이터를 넣거나 삽입하려고 할 경우 에러가 발생한다.
=> 따라서, 접근을 자주 해야하고 개수가 고정적인 데이터의 경우 배열을 사용하는 것이 적합하다.
4) 연산
- 읽기 & 쓰기
배열에서 인덱스를 통해 자료를 읽는 과정을 알아보자.
int A[4] = {2,4,0,5} 이러한 배열이 있을 때
A[2]를 읽으려고 하면 A[2] 자체의 값이 0인 것이 ]니라 A[2]의 주소를 가서 읽고 오는 것이다.
A[2]의 주소는 (A[0]의 주소) + 2*4byte 와 같이 계산된다.
만약 A[0]의 주소가 50 이었다면, A[2]의 주소는 58이 된다.( 이때 4byte는 정수의 용량을 의미한다.)
아래 식을 계산하는 연산의 처리 시간도 알아보자.
A[2] = A[2] + 1
위 식을 처리하기 위해서는 아래와 같은 순서로 연산이 처리된다.
(1) 오른쪽의 A[2]를 읽는다.
(2) +1 산술을 한다.
(3) 왼쪽의 A[2]에 그 결과를 대입(쓰기)한다.
이러한 연산들을 모두 처리하더라도 이는 모두 기본연산이므로 처리하는 데에 상수시간이 필요하므로
O(1)의 시간복잡도로 읽고 쓰기가 가능하다.
- 삽입 & 삭제
위의 읽고 쓰는 연산과 달리 배열에서 삽입과 삭제는 상수시간 내에 처리가 불가능하다.
새로운 데이터를 삽입하거나 기존의 데이터를 삭제하려면 배열의 연속적인 데이터를 유지해야 하는 특징으로 인해 O(n)의 시간복잡도를 가진다.
예를 들어
A = { 0, 1, 7, 3} 의 배열에서 A[2]를 삭제하려고 한다면 A[2]인 7을 삭제한 후, 그 뒤에 있는 데이터들을 다 앞으로 당겨와야한다. 이 예에는 당겨올 데이터가 A[3]인 3 뿐이지만, 크기가 큰 배열이라면 처리횟수가 더 커질 것이다.
2. 리스트
1) 순차적 자료구조이며 배열과 가장 큰 차이점은 메모리 상의 데이터가 비연속적이라는 점이다.
2) 인덱스 : 각 데이터를 나타내느 상수로 맨 앞의 인덱스는 0부터 시작하여 1씩 증가한다.
3) 각 언어별 리스트 유무 여부
- C : 리스트 X
- JAVA : 배열과 리스트 모두 지원 ( ArrayList / LinkedList)
- Python : 리스트만 지원
- Javascript : 배열에 리스트 기능 포함
6) 특징
리스트에서 가장 두드러진 특징은 데이터가 비연속적으로 메모리에 저장될 수 있다는 것이다.(각 데이터들이 객체로서 저장된다.)
따라서 정해진 크기만큼의 데이터만 저장되어 데이터가 적어도 크기에 변함이 없고, 초과되면 에러가 발생하던 배열과 달리 리스트는 크기가 가변적이어서 입력된 데이터만큼 크기가 지정되었다가 추가적으로 데이터가 삽입되거나 삭제되면 그에 크기가 맞추어진다.
5) 연산
- 읽기
인덱스 값을 통해 읽어오는 연산은 각 객체가 위치하는 주소를 읽어 그 주소로 가서 데이터를 읽어오는 것이다.
여기서 배열과 달리 객체라는 단어가 등장한 이유는, 리스트에서는 각 데이터가 객체로 메모리에 저장되기 때문이다.
- 삽입, 삭제
파이썬에서는 삽입은 append, 삭제는 pop을 이용한다.
이 때, 리스트에서도 배열과 마찬가지로 O(n)의 복잡도를 가진다.
읽기, 쓰기 , 삽입, 삭제 외에도 파이썬에서 리스트는 count, remove, index, insert 등 다양한 연산을 제공한다.
본 게시글은 한국외국어대학교 컴전학부의 신찬수 교수님의 유튜브 강의를 보고 학습한 내용을 작성한 학습기록입니다.
'Learning-log -CS > Data Structure & Algorithm' 카테고리의 다른 글
| 정렬 알고리즘 (0) | 2023.03.23 |
|---|---|
| 자료구조 - 큐(Queue), 데크(Deque) (1) | 2022.11.24 |
| 자료구조 - 순차적 자료구조 : 스택(Stack)(2022.09.22~10.12) (0) | 2022.10.12 |
| 자료구조 - 시간복잡도 , Big-O(2022.09.18) (1) | 2022.09.19 |
| 자료구조 - 자료구조와 알고리즘(2022.09.13) (2) | 2022.09.13 |
