Linked list, Stack, Queue <3-1>
<< 3주차 Lecture Note 1번째>>
- Abstract Data Types
- Array
Abstract Data Types
ADT란, 데이터 구조를 추상화한 것으로 아래의 특징을 가진다.
- 데이터의 저장: 어떤 데이터가 저장되는지 설명한다.
- 데이터의 운영: 데이터의 저장, 검색 등의 운영 방식을 설명한다.
- 오류 조건: 데이터 운영에서 발생할 오류를 정의하고 처리 방식을 설명한다.
Array
Array는 인덱스를 이용해 각 원소를 저장하는 방식으로,
파이썬의 리스트가 대표적이다.
1. Search Procedure in Array
위 그림의 Array에 'c' 라는 원소가 있는지 확인하는 작업을 한다면,
하나의 원소가 c와 동일한지 확인하는 작업을 Array의 전체 길이만큼 반복해서 모든 원소에 대해 확인함으로써 존재유무를 확정할 수 있다.
즉, Array의 전체 길이가 N 일 때, retrievals(작업 횟수)은 N이 된다.
2. Insert Procedure in Array
위 그림에서 'b'와 'd' 사이에 'c' 라는 원소를 새로 Insert 한다고 하면, 아래 코드의 절차를 따르게 된다.
y = list(range(len(x) + 1))
idx_insert = 2
val_insert = 'c'
for iter in range(0, idx_insert):
y[iter] = x[iter]
y[idx_insert] = val_insert
for iter in range(idx_insert, len(x)):
y[iter + 1] = x[iter]
이렇게 Insert 작업을 수행하면, Array에서 일어나는 원소확인 반복작업은
2) 에서 2회 → x[0:a-1] to y[0:a-1] (retrieval count: a)
3) 에서 1 → 'c' into y[a] (retrieval count: 1)
4) 에서 5 - 2 - 1 = 2 → x[a:] to y[a+1:] (retrieval count: n-a-1) 가 된다.
따라서, 위 리스트에서 새로운 원소 1개를 Insert 할 때의 retrievals은 5이다.
즉, 리스트에서 원소 1개를 Insert 할 때 retrievals는 리스트의 길이 N과 동일하다.
3. Delete Procedure in Array
Delete를 할 때에도 Insert처럼 제거할 원소 양옆으로 작업을 수행한다.
앞서 언급한 리스트에서 'd'를 제거하는 코드를 보자.
y = list(range(len(x)))
idx_delete = 3
for iter in range(0, idx_delete):
y[iter] = x[iter]
for iter in range(idx_delete, len(x)):
y[iter - 1] = x[iter]앞 리스트에서 'd' 의 인덱스는 3이므로, 새로운 리스트 y에서 인덱스 2까지 x를 카피하고,
인덱스 3에서 'e'부터 카피한다.
Insert는 새로운 원소를 추가하는 작업이 있었지만, Delete는 별도 작업이 존재하지는 않는다.
따라서, Delete는 Insert보다 retrievals가 1 작아진다. 즉 retrievals = N - 1이 된다.
4. Problems in Array
인덱스 기반의 Array에서, Insert나 Delete의 작업을 하는 경우,
앞에서 본 것과 같이 특정 1개의 원소에 대해서만 작업하더라도 약 N개의 작업이 수행되어야하므로 매우 비효율적이다.
이런 인덱스 기반 데이터 저장 방식의 문제점을 해결하기 위해 나온 알고리즘이 Linked List 이다.
링크드 리스트는 인덱스 기반이 아니므로 특정 원소를 삽입할 때 삽입할 공간을 새로 만들어내는 알고리즘이다.
다음 강의에서 배워보자.