리스트(List)

List

[1,2,3]

[2,1,3]

[3,1,2]

위에 있는 리스트는 전부 다른 리스트이다. 같은 숫자로 이루어져있지만 순서가 다르기 때문이다.

하지만 위에 있는 예시가 Set이라면 전부 같은거다 왜냐하면 순서가 상관없기 때문이다. 

 

List 구현방법

-Array list (Array, Dynamic array  >>> Array List는 Dynamic array로 되어있고 Dynamic array는 Array로 되어있음)

ex) 파이썬에서 list

-Linked list(Node)

 

배열의 특징

-고정된 저장 공간

-순차적으로 데이터 저장

-배열을 선언하면 size가 정해지고(static array) size만큼 연속된 메모리를 할당 받아 data를 순서대로 저장하는 자료구조

 

시간복잡도도

int arr[3] = { 2, 4, 6}

위의 배열이 선언되면 int 크기인 4byte의 메모리 공간이 연속적으로 ram메모리에 3개 할당된다. 이때 배열 arr의 가정 첫번째 숫자 2에 대한 메모리 주소가 arr에 저장되어 있다. 저 배열에서 6을 꺼내려면 가장 첫번째 숫자 메모리 주소에서 4byte씩 두번 떨어진곳에서 데이터를 가져올 수 있다.  이렇게 첫 주소값을 알고 있다면 어떤 index에도 즉시 접근할 수 있는데 이것을 direct access 또는 random access라고 한다. 배열은 배열이 아무리 길어도 첫번째 데이터의 주소값만 알면 바로 접근할 수 있기에 O(1)의 시간 복잡도를 갖는다.

연속적으로 데이터가 저장되어 있기에 첫번째 데이터 주소값으로 즉시 접근할 수 있는 Array list와는 달리 Linked list는 메모리에 순차적이지 않고 연속적이지 않은 메모리 공간에 할당이 되어서 Linked list내의 값을 찾으려면 첫번째 데이터의 메모리에 있는 다음 데이터의 메모리 주소를 연산하고 다음 데이터 메모리에있는 그다음 데이터 메모리의 주소를 연산하게 되어 시간복잡도는 O(n)이 된다.

 

Static array의 한계

데이터 개수가 정해져 있는 경우에는 Static array를 사용하는것이 좋다. 하지만 선언시에 할당된 size보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않아서 문제가 될 수 있다. 그렇다고 매번 크기가 엄청 큰 배열을 선언하면 메모리 비효율이 발생한다. 이런 문제점을 해결할 수 있는게 dynamic array이다.

 

Dynamic array

배열을 선언하고 append()으로 계속 데이터를 넣다보면 할당된 저장 공간이 다차게 된다. 이때 원래 공간의 두배의 메모리를 할당(더블링)하고 원래 데이터를 거기로 옮긴다음 기존의 꽉찬 데이터는 삭제한다. 이것을 Resizing과정이라고 하고 이 과정의 시간복잡도는 O(n)이 된다. 

 

 

배열의 선언 및 초기화 > O(n)

ex)

arr = [1, 2, 3]

 

배열에서 특정 데이터 접근 및 수정 , 데이터 추가 > O(1)

ex0

arr[1]

arr[0]= 9

arr.append(8)

 

마지막 데이터 삭제 > O(1)

arr.pop()

 

중간에 데이터 추가, 삭제 > O(n)

arr.insert(1, 10)

arr.pop(2)

 

중간에 데이터를 추가하거나 삭제하면 추가나 삭제한 데이터 뒤에 있는 배열들을 전부 하나씩 앞으로 땡기거나 뒤로 밀어야 해서 O(n)이 나온다.