List : Array-Based List, Linked List

Array-Based List

 

Insert : inefficient in Array. O(n)

 

Array-Based List에서 insert 함수와 Remove 함수는 for문을 사용하므로 O(n)이 걸린다.

 

Array Based List

장점 : 

1. element의 위치를 안다면 O(1) 시간에 acccess 할 수 있다.

2. 프로그래밍하기 쉽다(배열 사용)

 

단점 : 

1. input size가 Array size(max size) 넘어가면 extra work가 필요하다.

2. insert가 worst case의 경우 O(n)이 걸리고 best case의 경우 O(1)이 걸리는데 gap이 너무 크다. remove도 마찬가지.

 

Space :

list size가 max size(Array size)와 비슷하다면 Space 사용에서 효율적이나 그렇지 않다면 남는 공간이 많아 비효율적이다.

 

Linked List

클랫스를 정의한다.

 

클래스에는 element를 가지고 있고, 다른 Link 객체를 가리키는 포인터를 가지고 있다.

 

필기한 글씨체가 상당히 악필이다..

Link class는 다음 Link를 가르키는 포인터밖에 가지고 있지 않기 때문에 만약 위 사진처럼 curr이 12를 가리키고 있는데 이 자리에 10을 element로 가지고 있는 Link 객체를 넣는다면 23이 10을 가리키게 할 수 없다.(앞에 있는 객체를 가리키는 포인터가 있다면 가능하다)

 

그래서 insert를 할 때 curr은 그대로 있고, curr이 가리키는 객체 뒤에 새로은 객체를 삽입한다.

여기서 head와 tail의 개념이 나오는데, head는 코딩하기 편하게 그냥 자리만 차지하는 역할이다.

 

insert의 순서이다. 먼저 curr 뒤의 객체를 가리키는 포인터를 가진 새로운 link 객체를 만든다. 그 후 이 curr이 가리키는 객체의 포인터를 새로 생긴 객체를 가리키게 하면 insert는 완료가 된다.

 

removal에서는 그냥 curr이 가리키는 객체의 next 포인터를 다다음 객체를 가리키게 만들면 된다.

간단하게 쓰면

curr.setNext(curr.next().next())
이렇게 한줄에 끝난다.

 

Linked List의 단점은 특정한 element에 접근할 때 O(n)이 걸린다. 당장 prev만 하더라도

while(temp.next() != curr)

  temp = temp.next();

를 하여 prev를 한다.

 

표로 정리하면 다음과 같다.

 

	Array Based List	Linked List
Insertion and Deletion	O(n)	O(1)
Prev / access to an element	O(1)	O(n)
Pre-allocate space	Yes	No
Additional space overhead	No	Yes(pointer)

 

Space Comparison

Space 관점에서 Array Based List와 Linked List 중 어느 것이 더 좋을지 비교하는 point가 있다.

"Break-even" point :

DE = n(P+E)

n = DE/(P+E)

 

D : Number of maximum elements in array

n : Number of elements in linked list

E : Space for data value

P : Space for pointer

 

Break-even point는 Linked List가 사용하는 space와 Array-based List가 사용하는 space가 같아지는 원소의 개수를 나타낸다. 만약 n이 DE/(P+E)보다 커진다면 Array based List를 사용하는 것이 Space 측면에서 더 나을 것이다.

 

 

Freelists

Linked List에서 객체를 지우고 추가할 때 freelist를 만들어서 관리하면 더 빠르게 사용할 수 있다.

new와 garbage collection이 느리기 때문.

 

객체를 release할 때 freelist에 추가해주고, add를 할 때는 freelist에서 객체를 가져온다.

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업