List->Array->List->Array……
에러가 날때마다 영문도 모른체 데이터의 자료형을 변환하는데 급급했나요?
두 자료구조의 차이점을 몰라서 에러가 날때마다 적당히 자료형을 바꾸며 돌려막기한다면,
계산 시간과 한숨을 엄청나게 낭비하게 됩니다.
이제 이 답답함에서 벗어나보자구요!

# What I did before
list = []
array = np.array(list)
listagain = list(array)

시작은 리스트였으나,
np.where을 사용해서 원하는 값의 index를 찾으려다가,
error 때문에 list->array로 바꾸어 사용하다가,
array에 값을 추가하고 싶은데 list.append()가 생각나서,
다시 list로 바꾸어 사용해보셨나요?

여러분은 아닐지 몰라도 저는 자주 그랬습니다ㅎㅎ….
그래서 오늘은 다양한 Data Structure(자료 구조) 중 선형 구조(linear Structure)에 속하는 Array와 Linked List를 비교 분석해봅니다.

자료 구조 이해의 필요성

효율적인 프로그램 작성을 목표로한다면 가장 중요한 것은 저장 공간의 효율성과 실행 시간의 신속성입니다 (정보처리기사 시나공 책).

우리가 메모리에 여러 개의 원소를 저장하고 싶을 때, 우리는 컴퓨터에게 공간을 요청합니다.
Array(배열)과 linked list(연결 리스트)는 원소를 저장하는 방법입니다.

Array 정의

Array(배열)는 동일한 자료형의 데이터들이 순서를 가지고 나열되어있는 집합입니다.
Array를 연속적인 메모리 공간에 저장됩니다.
따라서 길이가 N인 array를 지정하면 각 원소의 주소를 쉽게 알 수 있습니다.

장점

이러한 특징 덕분에 array에 들어있는 원소들에게 순서대로 0부터 N-1까지 번호표를 붙일 수 있습니다.
이때 번호표를 index라고 부르고, 번호표를 이용해서 원소들을 부를 수 있게 됩니다.
1. 메모리 이용 효율이 가장 좋다. Why? 메모리를 연속적으로 배정받기 때문.
2. 데이터에 임의 접근이 가능하다.
3. For loop처럼 원소마다 반복되는 작업을 하려 할때 적합하다.

단점

1. 데이터 추가가 어렵다.
Array는 정적인 자료 구조이므로 계속해서 데이터 늘어난다면, array는 전체 원소를 저장할 새로운 메모리(장소)를 찾게됩니다.
만약 100개의 이름을 저장해야하지만 0부터 99까지 이어져있는 메모리(장소)가 없다면, 배열을 만들 수 없습니다.

2. 데이터 삭제시 메모리가 빈 공간으로 남겨져 낭비된다.

예시

  • Student array에 신입사원들의 이름을 가나다 순으로 담아놨다면 3번째에 위치한 신입사원의 이름은 student(2)를 사용해서 간편하게 알아낼 수 있습니다.

  • 배열의 크기 N에 따라서 크기가 N인 1차원 배열, 크기가 NxN인2차원 배열로 부릅니다.

Linked list 정의

Linked list는 각 노드(data부분+ pointer부분)의 포인터에 다음 노드의 위치를 저장하여 데이터를 연결시키는 저장 방법입니다.
따라서 array와는 달리 데이터가 원소의 메모리를 임의의 어느 곳에나 둘 수 있습니다.

장점

1. 새로운 노드를 쉽게 삽입& 삭제할 수 있다.

단점

1. Array와 달리 n번째 원소를 한 번에 찾을 수 없다.
2. Array와 달리 각 노드에 data뿐만아니라 포인터 부분을 저장하므로 메모리 이용 효율이 나쁘다.
3. 데이터에 임의 접근이 불가능하다.

시간 복잡도 비교

Array 와 Linked list의 시간 복잡도를 Big O notation으로 표현한다면?

  Array Linked list
읽기 O(1) O(n)
앞에 삽입/삭제 O(n) O(1)
뒤에 삽입/삭제 O(1) O(n)
중간에 삽입/삭제 O(n) O(n)

Array에서 삽입이 O(n)인 이유? 뒤에 오는 모든 원소들의 위치를 바꿔야하기 때문입니다.