순차적 자료구조: 배열과 리스트

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록

https://www.youtube.com/watch?v=Lqd8o7vL2Z8&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=6

 

배열 (array) vs. 리스트(list) 파이썬

- 가장 기본적인 순차적인(sequential) 자료구조

 

C언어의 배열

C언어에서의 배열

A[2] = A[2] + 1은 기본연산만 포함하기 때문에 O(1)

A[2]의 주소: RAM

A[0] 주소 + 2 * 4bytes

100 + 8 = 108

 

배열은 읽기와 쓰기를 연산으로 제공. 기본시간 내에 다 수행할 수 있다.

 

파이썬의 리스트

A = [2, 4, 0, 5]

결정적인 차이: 객체가 다른 메모리에 저장됨

A[2] = A[2] + 1

0이 1로 바뀌는 것이 아님. 0은 어딘가에 남아있고 A[2]가 1이 저장된 곳의 주소를 가리킴.

 

A.append(6): 맨 뒤에 6을 삽입.

A.pop(): 맨 뒤의 값을 지우고 리턴.

A.pop(1): A[1]을 제거하고 리턴. 남아있는 값들이 한 칸씩 이동해서 비워진 곳을 메꿈.

A.insert(1,10): A[1]에 10을 삽입. 끼워넣는다고 보면 됨. 

A.remove(value): A에서 value 제거

A.index(value): value의 인덱스 리턴

A.count(value): value가 몇 번 등장하는지 리턴

 

읽기와 쓰기에 더불어 여러 연산을 제공

 

리스트: 용량 자동조절 (dynamic array)

import sys
A = []
print(sys.getsizeof(A))
A.append(10)

print(sys.getsizeof(A))

list class

capacity: 용량

n: 현재 저장된 값의 개수

A의 용량은 100이지만 저장된 값의 개수는 용량보다 작아야 함.

 

# append 함수의 내부 동작 구조

A.append(x):
	if A.n < A.capacity:
    	A[n] = x
        A.n = n+1
    else:
    	A.n == A.capacity
        B = A.capacity*2 크기의 리스트 새로 할당
        for i in range(n):   # O(n)
        	B[i] = A[i]
        del A
        A = B
        A[n] = x
        A.n = n + 1