[Data Structure] Array & List

do yeon kim·2022년 9월 4일

Array & List

Array는 가장 기본적인 순차적인 자료구조이다.
파이썬에서 따로 array라는 클래스를 import해서 사용할 수도 있다.

import array as arr
a = arr.array("데이터타입", [2,3,4])
print(a)

하지만 pyton에서는 array와 같은 역할을 하는 list라는 자료구조가 존재하기 때문에 list를 사용하면 된다.

C언어의 array는 값 자체를 저장한다면, pyton의 list는 객체를 가르키는 주소를 리스트에 저장한다. 새로운 값을 할당한다면, 원래 있던 값을 가르키던 주소가 새로운 객체를 가르키는 주소로 대체되는 것이다. 객체(값)이 사라지는 것이 아니다.

python의 list는 C언어의 array와는 다르게 다양한 메서드를 제공한다.

List capacity ( dynamic array)

C언어의 array의 해당 array의 크기 이상의 데이터가 들어가게 되면, 다시 array의 크기를 변경해주어야 한다.(malloc)

Python의 List는 C언어의 array와 다르다.
List는 자동으로 리스트의 용량을 변경시킨다.

import sys

a = []
print(sys.getsizeof(a)) # 56byte

a.append(1)
print(sys.getsizeof(a)) # 88byte

빈리스트의 경우 56byte가 기본적으로 할당된다.
그리고 데이터를 추가 할 때마다 리스트의 크기가 자동으로 증가한다.

순차적자료구조(Sequential Data Structures)

배열, 리스트
index로 임의의 원소를 접근할 수 있다.
Stack, Queue, Dequeue
제한된 접근(삽입, 삭제)만 허용한다.
Stack - LIFO
Queue - FIFO
Dequeue - Stack + Queue
Linked List
자기값 뿐만 아니라 다음값을 가르키는 주소도 가진다.

참고