[자바로 구현하고 배우는 자료구조] 2.선형 자료구조(연결 리스트&배열)(2)

1-3. 경계 조건

어떠한 자료구조든 다음의 경계조건을 고려해야한다.

(1) 자료구조가 비어있을 때(Empty data structure)

(2) 자료구조에 하나의 요소가 있을 때(Single element in the data structure)

(3) 자료구조의 첫번째 요소를 더하거나 제거할 때(Adding/removing beginning of data structure)

(4) 자료구조의 마지막 요소를 더하거나 제거할 때(Adding/removing end of the data structure)

(5) 중간 요소를 다뤄야 할 때(Working in the middle)

 

1-4. addFirst 메소드

public void addFirst(E obj){
	Node<E> node = new Node<E>(obj);
    node.next = head;
    head = node;
    currentSize++;
}

 

1-5. addLast 메소드

public void addLast(E obj){
	Node<E> node = new Node<E>(obj);
    if(head = null){
    	head = node;
        currentSize++;
        return;
    }
	Node<E> tmp = head;
    while(tmp.next != null){
    	tmp = tmp.next;
    }
    tmp.next = node;
    currentSize++;
}

 

1-6. removeFirst 메소드

public E removeFirst(){
	if(head == null)
    	return null;
	E tmp = head.data;
    if(head == tail){
    	head = tail = null;
	}else{
    	head = head.next;
	}
	currentSize--;
    return temp;
}

 

1-7. removeLast 메소드

public E removeLast(){
	if(head == null){
    	return null
	}
    if(head == tail){
    	return removeFirst();
    }
    Node<E> current = head.previous = null;
    while(current != tail){
    	previous = current;
        current = current.next;
    }
    previous.next = null;
	currentSize--;
    return current.data;
}

 

1-8. remove와 find

첫번째 요소나 마지막 요소가 아니라 제거하고자하는 요소를 제거하는 remove 메소드와 찾고자하는 요소가 있는지 확인하는 contains 메소드가 있다.

public E remove(E obj){
	Node<E> current = head.previous = null;
    while (current != null){
    	if(((Comparable<E>)current.data).compareTo(obj)) == null){
        	if(currnet == head){
            	return removeFirst();
            }
            if(current == tail){
            	return removeLast();
            }
            currentSize--;
            previous.next = current.next;
            return current.data;
        }
        previous = current;
        current = current.next;
    }
    return null;
}

public boolean contains(E obj){
	Node<E> current = head;
    while(current != null){
    	if(((Comparable<E> obj).compareTo(current.data)) == null){
        	return true;
        }
        current = current.next;
    }
    return false;
}

 

1-9. peek 메소드

peek 메소드는 연결 리스트의 내용을 읽어 찾고자 하는 요소가 있는지 확인하는 메소드이다.

public E peekFirst(){
	if(head == null){
    	return null;
    }
    return head.data;
}
public E peekLast(){
	if(tail == null){
    	return null;
    }
    return tail.data;
}

 

1-10. 연결리스트 테스트

연결리스트를 만들어 지금까지 작성한 메소드를 테스트 할 수 있다.

public class Test{
	public static void main(String[] args){
    	static ListI<Integer> list = new LinkedList<Integer>();
        int n = 100;
        for(int i=0 ; i < n ; i++){
        	list.addFirst(i);
        }
        for(int i=n ; i >= 0 ; i--){
        	int x = list.removeFirst();
        }
    }
}

 

1-11. 반복자

public class LinkedList<E> implements ListI<E>{
	class IteratorHelper implement Iterator<E>{
    	Node<E> inext;
        public IteratorHelper(){
        	index = head;
		}
        public boolean hasNext(){
        	return index != null;
        }
        public E next(){
        	if(!hasnext()){
            	throw new suchElementException();
                E val = index.data;
                index = index.next;
                return val;
            }
        }
    }
}

 

1-12. 이중 연결 리스트

C.next가 tail 포인터를 가리켜야하는데 빼먹었다,,,

 이중 연결 리스트는 기존의 next 포인터와 data만 갖던 노드에 이전 노드를 가리키는 prev 포인터가 추가했다. 

 

1-13. 원형 연결 리스트

 원형 연결 리스트는 마지막 노드의 next 포인터가 연결리스트의 노드를 가리키는 연결 리스트이다. iterator를 이용하여 head에서 시작한 연결 리스트가 다시 head로 돌아오는지 메모리의 주소를 비교하여 확인할 수 있다. 임시 포인터 t를 만들어서 노드를 A-B-C ... 로 이동할 때마다 t 포인터를 함께 이동시킨다. iterator로 세 가지 조건을 이용하여 다시 head와 만다는지 확인할 수 있다. t == null / t == head / t.next == head. 이 때 임시 포인터 t가 모든 노드를 지나가야하므로 시간복잡도는 O(n)이다. 하지만 tail 포인터를 만들면 바로 tail 포인터가 가리키는 곳으로 가면 되기때문에 O(1)의 시간복잡도를 갖는다.

 

 하지만 마지막 노드가 head 포인터가 가리키는 노드가 아니라 임의의 노드를 가리킨다면? tail포인터로 가서 마지막 노드가 tail 포인터를 가리키는지 확인해야하므로 O(n)의 시간복잡도를 갖는다. tail 포인터가 아니라 임시 포인터 2개와 currentSize를 이용하면 시작점에서 currentSize만큼 떨어진 노드로 이동하고, 남은 포인터로 그 포인터가 올 때까지 이동한다. 이 때 시간복잡도는 O(n^2)이다.

 

2-1. 스택과 큐

 위 그림 속 배열에 25 다음에 30을 추가하는 addLast()의시간복잡도는 상수로 O(1)이다. 25 다음의 30을 삭제하는 removeLast()의 시간 복잡도도 상수로 O(1)이다. 하지만 위 배열에 0을 처음에 넣거나 삭제한다면? 추가하는 경우 크기가 같은 새로운 배열을 만들고, 그 배열의 첫번째 자리에 0을 넣은 뒤 기존의 배열에 있던 숫자를 새로 추가해야하기 때문에 addFirst()의 시간복잡도는 O(n)이다. addFirst와 마찬가지로 새로운 배열을 만들고, 그 배열에 0을 제외한 나머지 숫자를 입력해줘야 하므로 addLast()의 시간복잡도도 O(n)이다.

 

 그렇다면 이 배열로 Stack과 Queue를 만든다고 생각해보자. Stack은 후입후출(LILO, Last In Last Out)이다. push는 addLast이고 pop은 removeLast이다. Stack의 시간복잡도는 O(1)이다. Queue는 후입선출(LIFO, Last In First Out)이다. addLast와 removeFirst 메소드를 이용할 것이다. addLast의 시간복잡도는 O(1), removeFirst의 시간복잡도는 O(n)이므로 배열로 큐를 구현할 수 없다.

 

 배열과 연결 리스트는 각각의 장단점을 갖고있다. 배열은 배열의 요소에 빠르게 접근할 수 있고 메모리를 적게 사용한다는 장점이 있지만 크기가 고정되어있고, 배열의 크기를 빠르게 늘려야 한다(rapid growth). 연결 리스트는 크기의 제한이 없지만 느리고 여분의 메모리가 필요하다는 단점이 있다.