List, Stacks, and Queues
1. List
1-1. 정의
유한하고, 순서가 정해져있는 자료구조
List의 element는 위치가 정해져있다.
1-2. Implementation concept
current position의 컨셉을 가지고 있다.
Operation은 curr_pos에 근거해서 일어나게 된다.
1-3. Array-based List
: array를 이용하여 만든 list
장점 :
설치하기/이해하기 쉽다.
빠르게 특정 위치의 element에 접근하기 쉽다.
access만 하고 insert나 remove가 안되는 application의 경우 Linked list에 비해 빠르다.
linked list에 비해 메모리를 적게 쓸 수도 있다.(pointer를 저장할 필요가 없기 때문에)
약점:
insert와 remove에 Θ(n)의 시간이 든다.
메모리를 미리 할당해야 한다.
array가 꽉차면 더 큰 메모리를 할당해야 한다.
1-4. Array-based Implements
class AList<E> implements List<E> {
private static final int defaultSize = 10;
private int maxSize;
private int listSize;
private int curr;
private E[] listArray;
AList() { this(defaultSize); }
AList(int size){
maxSize = size;
listSize = curr = 0;
listArray = (E[])new Object[size];
}
public void clear(){ listSize = curr = 0; }
public void moveToStart() { curr = 0; }
public void moveToEnd() { curr = listSize; }
public void prev() { if(curr != 0) curr--; }
public void next() { if(curr < listSize) curr++; }
public int length() { return listSize; }
public int currPos() { return curr; }
public void moveToPos(int pos){
assert (pos >= 0) && (pos <= listSize) :
"Position out of range";
curr = pos;
}
public E getValue() {
assert (curr >= 0) && (curr < listSize):
"No current element";
return listArray[curr];
}
}
1-5. Array-based Implements(insert, append, remove)
/*Insert "it" at current position*/
public void insert(E it) {
assert listSize < maxSize :
"List capacity exceeded";
for(int i = listSize; i > curr; i--){
listArray[i] = listArray[i-1];
}
listArray[curr] = it;
listSize++;
}
/* append "it" end point */
public void append(E it) {
assert listSize < maxSize :
"List capacity exceeded";
listArray[listSize++] = it;
}
/* Remove and return removed element */
public E remove(){
if((curr < 0) || (curr >= listSize))
return null;
E it = listArray[curr];
for(int i = curr; i < listSize - 1; i++)
listArray[i] = listArray[i+1];
listSize--;
return it;
}1-6. Link
Link class
다음 Link를 알려주는 pointer와 값을 저장하는 class
class Link<E> {
private E element;
private Link<E> next;
Link(E it, Link<E> nextval)
{ element = it; next = nextval; }
Link (Link<E> nextval) { next = nextval; }
Link<E> next() { return next; }
Link<E> setNext(Link<E> nextval)
{ return next = nextval; }
E element() { return element; }
E setElement(E it) {return element = it; }
}1-7. Linked List
Linked List에서는 curr link 뒤쪽에 삽입되고 삭제되게 된다.(link가 next link를 지목하기 때문)
그래서 첫번째 head는 null값을 저장하는 것으로 하나 만들어둔다.
class LList<E> implements List<E> {
private Link<E> head;
private Link<E> tail;
protected Link<E> curr;
int cnt;;
LList(int size) { this(); }
LList() {
curr = tail = head = new Link<E>(null);
cnt = 0;
}
public void clear(){
head.setNext(null);
curr = tail = head = new Link<E>(null);
cnt = 0;
}
public void moveToStart() { curr = head; }
public void moveToEnd() { curr = tail; }
public int length() { return cnt; }
public void next() {
if (curr != tail) { curr = curr.next(); }
}
public E getValue(){
assert curr.next() != null :
"Nothing to get";
return curr.next().element();
}
}/* Insert "it" at current position */
public void insert (E it) {
curr.setNext(new Link<E>(it, curr.next()));
if(tail == curr) tail = curr.next();
cnt++;
}
public void append(E it) {
tail = tail.setNext(new Link<E>(it, null));
cnt++;
}
/* remove and return the removed item */
public E remove() {
if(curr.next() == null) return null;
E it = curr.next().element();
if (tail == curr.next()) tail = curr;
curr.setNext(curr.next().next());
cnt--;
return it;
}prev/get/set 을 하는 것이 tidious 함
/* Move curr one step left;
no change if already at front*/
public void prev(){
if (curr == head) return;
Link<E> temp = head;
while (temp.next() != curr)
temp = temp.next();
curr = temp;
}
/* Return position of the current element */
public int currPos() {
Link<E> temp = head;
int i;
for(i = 0; curr != temp; i++)
temp = temp.next();
return i;
}
/* Move down list to "pos" position */
public void moveToPos(int pos){
assert (pos>=0) && (pos<=cnt) :
"Position out of range";
curr = head;
for(int i = 0; i < pos; i++)
curr = curr.next();
}1-8. Array-based List와 Linked List의 비교
insert/remove : Θ(n) / Θ(1)
prev/access to an element : Θ(1) / Θ(n)
pre-allocate space : yes / no
Additional space overhead : no / yes
1-9. Break-even point
언제 link보다 array가 memory 사용량이 적은가?
"break-even" point가 존재
D : # of maximum elements in array
n : # of elements in linked list
E : Space for data value
P : Space for pointer
DE = n(P+E)
$n = \frac{DE}{P + E}$
1-10. Freelists
new를 사용하게 되면 새로운 메모리 공간을 할당하게 됨.
사용하지 않는 링크는 garbage collection으로 처리되지만 느림
그래서 freelist를 사용해줄 수 있음!
제거되는 list를 freelist로 따로 저장해둔다!
<freelist 설정 방법>
static Link freelist = null;
/* freelink가 있다면 freelist 하나를 return */
static <E> Link<E> get(E it, Link<E> nextval) {
if(freelist == null)
return new Link<E>(it, nextval);
Link<E> temp = freelist;
freelist = freelist.next();
temp.setElement(it);
temp.setNext(nextval);
return temp;
}
void release() {
element = null;
next = freelist;
freelist = this;
}public void insert(E it) {
curr.setNext(Link.get(it, curr.next()));
if(tail == curr) tail = curr.next();
cnt++;
}
public E remove() {
if(curr.next() == null) return null;
E it = curr.next().element();
if (tail == curr.next()) tail = curr;
Link<E> tempptr = curr.next();
curr.setNext(curr.next().next());
tempptr.realease();
cnt--;
return it;
}1-11. doubly linked list
Double Link : 앞과 뒤의 포인터를 모두 저장하는 링크
class DLink<E> {
private E element;
private DLink<E> next;
private DLink<E> prev;
DLink(E it, DLink<E> p, DLink<E> n)
{ element = it; prev = p; next = n; }
DLink(DLink<E> p, DLink<E> n)
{ this(null, p, n); }
DLink<E> next() { return next; }
DLink<E> setNext(DLink<E> nextval)
{ return next = nextval; }
DLink<E> prev() { return prev; }
DLInk<E> setPrev(DLink<E> prevval)
{ return prev = prevval; }
E element() { return element; }
E setElement(E it) { return element = it; }
}
// with fixed tail node
public void insert(E it){
curr.setNext(new DLink<E>(it, curr, curr.next()));
curr.next().next().setPrev(curr.next());
cnt++;
}
public void remove(){
if(curr.next() == tail) return null;
E it = curr.next().element();
curr.next().next().setPrev(curr);
curr.setNext(curr.next().next());
cnt--;
return it;
}
// without fixed tail node
public void insert(E it){
curr.setNext(new DLink<E>(it, curr, curr.next()));
curr.next().next().setPrev(curr.next());
if(tail == curr) tail = curr.next();
cnt++;
}
public void remove(){
if(curr.next() == tail) return null;
E it = curr.next().element();
if(tail == curr.next()) tail = curr;
if(curr.next().next() == != null)
curr.next().next().setPrev(curr);
curr.setNext(curr.next().next());
cnt--;
return it;
}
prev()의 경우 Θ(1)만에 수행할 수 있게 된다.
그래서 head와 tail을 두개 모두 고정된 링크로 만들어 놓게 된다.(둘 다 자료값은 null을 담고 있음)
2. Stack
2-1. Concept
LIFO : Last in, First out
restricted list : end of list에서만 insert와 remove가 일어나는 형태
push(), pop(), top()으로 나뉘어진다.
2-2. Array-based stack
- 모든 operation Θ(1)에 수행 가능
- top은 마지막 위치를 가르친다. => 값을 꺼내주기 위해
2-3. Linked stack
- 모든 operation Θ(1)에 수행 가능
- array-based stack에 비해 pointer 값을 추가로 저장해야되므로 2배의 메모리가 사용된다.
- top을 링크로 저장
3. Queue
3-1. Concept
FIFO : First in, First out
restricted list : end of list에만 insert이 일어나고 front of list에만 remove가 일어난다.
3-2. Implementation
: array-base로 하게 되면 저장된 array 공간을 넘어서는 현상이 생기게 된다.
dequeue 시에는 front 포인터를 증가시키고(앞의 element를 빼냄)
enqueue 시에는 rear 포인터를 증가시킨다.
만약 n개의 최대 사이즈를 가지는 queue에 n개의 array로 구현하게 되면, 아무것도 없는 상태와 queue가 꽉차있는 상태의 front와 rear 포인터 포지션이 겹치게 된다!
해당 상황을 없애주기 위해 n개의 size를 가지는 queue는 n+1로 구현한다.
class AQueue<E> implements Queue<E> {
private static final int defaultSize = 10;
private int maxSize;
private int front;
private int rear;
private E[] listArray;
AQueue() { this(defaultSize); }
AQueue(int size) {
maxSize = size+1;
rear = 0; front = 1;
listArray = (E[])new Object[maxSize];
}
public void clear()
{ rear = 0; front = 1; } //zero state
public void enqueue(E it){
assert ((rear + 2) % maxSize) != front : "Queue is full"; // full state
rear = (rear + 1) % maxSize;
listArray[rear] = it;
}
public E dequeue() {
assert length() != 0 : "Queue is empty";
E it = listArray[front];
front = (front + 1) % maxSize; //circular situation
return it;
}
public E frontValue() {
assert length() != 0 : "Queue is empty";
return listArray[front];
}
public int length() {
return ((rear + maxSize) - front + 1) % maxSize;
}
}4. Dictionary
search key와 value(record)로 이루어진 자료 구조
search key는 값을 찾기 위한 단서(?) => 어레이로 치면 위치 정도가 되겠다.
key 값과 record 값을 분리하기 위해 딕셔너리에서는 각각의 자료를 (key, record)의 pair로 저장하게 된다.
sorted가 되어있는 dictionary의 경우
- search 시에 binary search를 사용하면 되어서 빠르게 검색할 수 있다. => $\Theta(\log n)$
- 그러나 insertion에 많은 시간이 소요된다. => $\Theta(n)$
- remove는 $\Theta(n)$
unsorted의 경우
- search => $\Theta(n)$
- insertion => $\Theta(1)$
- remove => $\Theta(n)$