[자료구조] #10 List(1)

• List vs Deque(Stack or Queue)

 

공통점 : 1차원 배열에 데이터를 저장한다.

차이점 : 임의의 포지션에서 연산이 가능하다.
(Index로 주어지는 위치에서 삽입/삭제 가능)

 

• 부가연산

empty(): 리스트가 비어있으면 true를 반환한다.
full() : 리스트가 가득 차있으면 true를 반환한다.
size() : 리스트의 아이템들의 개수를 반환한다.

 

• 메인연산

insert(i, item) : 새로운 아이템을 i번째 위치에 삽입한다.
remove(i) : i번째 위치의 아이템을 삭제한다.
get(i) : i번째 위치의 아이템을 반환한다.
replace(i, item) : 아이템과 i번째 위치의 아이템을 교체한다.
find(item) : 아이템의 인덱스(위치)를 반환한다.
*find(itme)은 관용적으로 첫번째 나타난 것의 위치를 가리킨다.(정책)

 

• ArrayList vs LinkedList

ArrayList : 배열을 이용한다.

쉽게 구현할 수 있지만, 저장할 수 있는 아이템의 개수가 한정되어 있다.

 

LinkedList : 포인터를 이용한다.

저장에 제한을 두지 않지만, 포인터에 따른 자원을 소모하게 된다.

 

결국 둘다 사용하니까 필요에 따라 사용하는 것이 중요하다!

 

• ArrayList 구조

 

ArrayList : 1차원 배열에 아이템을 저장한다.

[MLS](MAX_LIST_SIZE)에 아이템을 저장한다.

 

length : 마지막 아이템을 가리키는 용도이다.

 

• ArrayList : empty / full / insert / remove

 

empty() : length == 0

full() : length == MLS

 

insert(i, item)

유효한 인덱스 범위 : 0 ~ length (마지막에도 추가할 수 있다.)

remove(i)

유효한 인덱스 범위 : 0 ~ length-1 (빈공간을 제거할 수 없기 때문이다.)

 

• 시간복잡도 분석

 

insert / remove / find / get / replace의 Worst case를 분석해보자. 

• insert : 맨 앞의 아이템을 삽입하는 경우 (T(n) ∈ O(n))
• remove : 맨 앞의 아이템을 삭제하는 경우 (T(n) ∈ O(n))
• find : 입력으로 주어진 아이템이 없는 경우 (T(n) ∈ O(n))
• get / replace : 배열을 사용했기 때문에 상수시간이 걸린다. (T(n) ∈ O(1))

• Singly Linked List(단순 연결 리스트)

 

단순 연결 리스트의 각 데이터는 노드로 표현되고 각 노드는 데이터와 다음 데이터를 가리키는 링크로 이루어져 있다.

시작 노드를 가리키는 포인터인 헤드 포인터가 있고, 맨 마지막 노드는 nullptr 또는 null로 표시된다.

노드의 순서는 암묵적으로 정해진다.

 

insert(i, item)

Step 1) head에서 (i-1)노드로 이동한다. (search)

Step 2) (i-1)노드를 새로운 노드와 연결한다.

Step 3) 새로운 노드(p)를 (i)노드와 연결한다. (task)

remove(i)

Step 1) head에서 (i-1)노드로 이동한다. (search)

Step 2) (i-1)노드를 i 옆에 있는 노드와 연결한다.

Step 3) (i) 노드를 제거한다. (task)

 

Worst case : 제일 마지막에 있는 아이템 insert/remove 할 때

 

get(i) / replace(i, item)

head에서부터 (i) 노드로 이동한다. (search)

get(i) : 노드에서 값을 리턴한다. (task)

replace(i, item) : 아이템의 값을 대체한다. (task)

 

Worst case : 제일 마지막에 있는 아이템 get/replace 할 때

 

배열과는 다르게 head에서 차례차례 이동하는 방식이 단점이 될 수 있다.

 

find(item)

head부터 출발해서 각 노드와 찾는 값을 비교한다.

 

Worst Case : 주어진 아이템이 없을 때

 

• 특수한 상황

front/rear에 아이템을 insert/remove 할 때

 

Array List

insert/remove rear : efficient (O(1))

insert/remove front : inefficient(O(n))

 

Singly Linked List

insert/remove rear : inefficient (O(n))

insert/remove front : efficient(O(1))

 

Array List vs Singly Linked List

Array List는 get/replace 할때 더 효율적이다.

SLL은 아이템이 지속적으로 추가되는 것을 가능하게 하지만 포인터를 사용하기 때문에 2배의 공간을 필요로 한다.

 

• 정리