List - Array list vs Linked list

리스트

List 와 Set의 차이

• List는 순서가 중요한 자료구조이다.
  • [1,2,3] ≠ [3,2,1]
• Set은 순서가 중요하지 않은 자료구조이다
  • (1,2,3) = (3,2,1)

파이썬의 List

• 자료구조 List ≠ 파이썬의 List
• 파이썬의 LIst = Array List임.
• 파이썬의 Array List는Dynamic Array로 구현되어 있는데, Dynamic Array는 Array로 구현되어 있음

Array List vs Linked List

• Array list는 메모리 구조상 변수가 순차적으로 할당
• Linked list는 각 노드가 메모리 상 따로 저장되어 있고, 이를 Link로 잇는 형태

배열 (Array)

배열의 특성

1. 고정된 저장 공간(fixed-size)
2. 순차적인 데이터 저장(order)

배열의 정의

• 배열은 선언시 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속/순차적으로 저장하는 자료구조

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

• 위의 예시에서는 배열의 사이즈를 5로 정했기 때문에 int형 데이터 4byte 5개를 저장할 메모리 공간인 20byte를 미리 할당받는다. 이처럼 고정된 size를 갖게 되기 때문에 static array라고 부른다.
  • int형 = 4byte
  • 1byte = 8bit
  • 1 GB = $1000^3$byte
    
• 또한 배열의 데이터를 연속적이고 순차적으로 메모리에 저장

Random access

• 메모리에 저장된 데이터에 접근하려면 주소값을 알아야 한다.
• 배열변수는 자신이 할당받은 메모리의 첫 번째 주소값을 가리킨다.
• 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능한다
• 이를 direct access 또는 random access라고 부른다.
• 첫 번째 데이터가 저장된 주소값이 0x4AF55라면 두번째 데이터는 0x4AF55 + 41에 저장이 되어있고, n번째 데이터는 0x4AF55 + 4(n-1)에 저장이 되어있다.
• 아무리 긴 배열이라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있어서 O(1)의 시간복잡도를 갖는다
• Linked list는 메모리상에서 연속적으로 저장되어 있지 않기 때문에 random accesss가 불가능하다. n번째 데이터에 접근하기 위해서 **array**의 시간복잡도는 **O(1)** 이지만 , **linked list**는 n번의 연산을 해야하므로 시간복잡도는 **O(n)**이 된다.

Static array의 한계

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

Dynamic Array

Dynamic Array 정의

• 선언 이후에 size를 변경할 수 없는 정적배열(Static Array)과 다르게 동적배열(Dynamic Array)는 size를 변경(resizing)할 수 있다.
• fixed-size인 Static Array의 한계점을 보안하고자 고안되었다.

Dynamic Array의 변수할당과 Resizing 과정

• 사이즈가 10인 배열에 순차적으로 13개의 변수를 할당한다고 하자.
• 동적배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, Resizing을 하게 된다.
• 데이터를 추가할 때는 **O(1)** 의 시간복잡도이지만, 배열의 크기를 늘리는 Resizing은 **O(n)**의 시간복잡도가 소요된다.
• Resizing은 기존의 배열보다 두배 큰 배열을 만들고, 이전 배열에서 새로운 배열로 각 데이터를 옮기게 된다. 이후 기존의 배열은 삭제한다. 이 과정에서 **O(n)** 의 시간복잡도가 발생하는 것이다.
• Resizing을 두배로 하는 이유는, Resizing이 O(n)의 시간복잡도를 요구하기에 크기를 1만큼씩 늘리게 되면 많은 시간복잡도가 요구된다. 반면 큰 사이즈의 배열을 만들지 않는 이유는 메모리 낭비가 발생하기 때문이다.
• 이렇게 2배 큰 크기로 Resizing 하는 것을 더블링(Dubling)이라고 한다.

Dynamic Array의 사용법

• 선언시에 배열의 크기를 정하지 않아도 되기 때문에 코딩테스트에서 dynamic array를 자주 사용하게 된다.
• Python에서는 list 자료형을 통해 dynamic array를 이미 잘 구현해 두었기에 직접 dynamic array를 구현할 필요없이 list 자료형을 사용하면 된다.
• 즉 문제에서 배열을 사용해야 하는 경우에는 list 를 사용하면 된다.
• 우리가 익혀야 할 것은 list의 연산(operation) 들과 시간복잡도 이다.

List 연산

• append(x) : 리스트의 맨 마지막에 x 추가
• sort() : 리스트의 요소를 순서대로 정렬
• reverse() : 현재 리스트를 그대로 거꾸로 뒤집는다.
• index(x) : x값에 해당하는 인덱스 리턴. 인덱스를 구하기 위한 함수!
• insert(idx, x) : idx위치에 x값을 삽입
• remove(x) : 리스트에서 첫 번째로 나오는 x를 삭제 (값 기준)
• pop() : 맨 마지막 요소 리턴하고 리스트에서 삭제
• cound(x) : 리스트 안에 x가 몇 개 있는지 조사하여 개수 리턴
• extend(array) : 원래 리스트에 array를 추가

  a = [1,2,3]
  a.extend([4,5])
  >>> [1, 2, 3, 4, 5]
  
  b = [6, 7]
  a.extend(b)
  >>> [1, 2, 3, 4, 5, 6, 7]

Array List의 시간복잡도

• 파이썬에서는 Array List를 Static array와 Dynamic array로 구현했다.
• 선언과 초기화 : **O(n)**
• Dynamic array에서 원소를 뒤에 추가할 때 리사이징이 필요하다면 O(n)의 시간복잡도가 걸리지만, 보통은 O(1)이다. 그렇기에 이런경우 분활상환기법을 사용하여 O(1)이라고 표기한다.
• 중간에 데이터를 추가하게 될 경우, 그 인덱스 이후의 데이터들은 한칸씩 밀어야 하기 때문에 n만큼의 시간복잡도 요구
  
• *Amortized : 분할상환