리스트(List)

** 자료구조 : 데이터를 저장하고 관리하는 방식

 

List 자료구조는 SET 자료구조와 비교가 많이 된다.

예를 들어, 1,2,3을 저장하려고 한다.

 

# SET 자료구조

set에 저장할 때는 (1,2,3)으로 저장을 하든, (3,2,1)로 저장하든, (2,3,1)로 저장하든 다 똑같다.

원소가 무엇이 저장이 되어있느냐가 중요하다. 순서는 중요하지 않다.

 

# List 자료구조

하지만, List는 순서가 중요한 자료구조.

[1,2,3], [3,1,2]는 전혀 다른 리스트가 된다.

순서가 중요하기 때문에 순서가 바뀌면 전혀 다른 list가 된다.

 

## List 자료구조 구현방법

List 자료구조는 어떻게 구현이 될까?

크게 두 가지 방법이 있다.

 

1/ Array List

- Array로 만들어진 list. 배열을 기반으로 만들어져있다.

만약 1,2,3이 저장이 되어 있다면, 1,2,3 순서대로 저장된다.

 

2/ Linked List

- 메모리상에 비연속적으로 저장되어있는 node들에 1,2,3 이렇게 저장이 되어서 연결을 해 이 순서대로 저장이 되게끔 하는자료구조.

- Array List로도 list를 구현할 수 있고, Linked List로도 list를 구현할 수 있다.

 

 

## Python에서의 List 자료구조

여기서 헷갈리면 안되는게 있다.

Python을 사용할때 List 자료구조와 여기 List는 다르다.

자료구조에서 분류할 때 사용하는 List이고, Python에서 쓰는 List는 사실 Array List를 list라고 부르는 것 뿐.

Python에서 list를 쓸 때는 Array List를 쓴다고 인지하면 되고, Linked List를 쓰는 상황이 오면 따로 node를 구성해서 직접 만들어줘야한다.

Array List는 이미 Python에서 list라는 자료구조로 구현이 되어있기 때문에 그냥 list를 가져다쓰면 된다.

 

 

Python에서 Array List는 무엇으로 구현이 되어있을까?

Array로 구현할 수 있고, Dynamic array로 구현을 할 수 있다. Array, Dynamic Array부터는 C언어의 영역이다.

그래서 Python 언어를 사용한다면 문제에서 배열을 써야된다고 하면, 직접 Array, Dynamic array를 쓰지는 못하니 그냥 Array list(List)를 쓰면 되겠구나 생각하면 된다.

 

 

### Array list 연산

Array list에 연산들이 있다. append, insert 등의 연산들을 쓸 수 있는데 그 연산들의 시간복잡도를 알기 위해서는 Array, Dynamic array 즉, 밑바탕부터 이해해야한다. Array, Dynamic array를 순차적으로 배우고 그것들로 구성된 Array List의 연산들은 시간복잡도가 어떻게 되는지 알아보자.

 

Python의 list, 즉 Array list는 Dynamic array를 통해서 구현된다. Dynamic array는 Array를 통해서 구현된다. 결국 서로 얽히고 얽혀있다.

 

 

# 정리

다시 정리하면,

자료구조에서 List로 분류된 이 자료구조는 Array List로도 구현할 수 있고, Linked List로도 구현할 수 있다.

Python에서 Array List는 이미 List라는 자료구조 이름으로 구현되어있다.

Array List는 Array, Dynamic array로 구현이 될 수 있는데, Python에서는 Dynamic array로 구현이 되어있고, Dynamic array는 사실 Array로 구현된 것.

그래서 우리는 Array를 이해해야하고, Dynamic array를 이해하면, Python에서 (Array) List 자료구조를 이해할 수 있다.

 

 

**출처 : 모든 내용은 인프런의 '코딩테스트 [ALL IN ONE]'강의를 기반으로 작성하였습니다.