Collection Framework(2)

3. LinkedList

ArrayList와 LinkedList 모두 List라는 interface로 부터 상속 받아 구현되어져 있다. 하지만 두 List는 구현 방식이 다르고 성능도 다르다.

ArrayList에 대해서 회고하여보면 ArrayList는 정말 배열 그자체로 연속적인 공간이 배정이 된다.

반면 LinkedList는 데이터들이 다음 객체의 주소를 가지고 있어서 객체가 서로 이어져 있다.

class Node {
	Node next; // a link to the next element
	Object obj; // data
}

그래서 LinkedList라고 불리는 이유가 인스턴스간의 연결이 되어 있어서 이다.

Addition and deletion with linked lists

그러면 LinkedList를 사용하는 이유는 무엇인가? 삽입삭제가 효과적이기 때문

• Deleting an element from the linked list
  
  삭제할때 그냥 주소만 바꾸어주면 된다.

반면 ArrayList는 중간에 비어둘 수 없기 때문에 삭제된 데이터를 기준으로 그 뒤에 있던 모든 데이터는 앞으로 한 칸씩 움직여야 하기에 많은 시간 소모가 발생하게 된다.

• Adding an element to the linked list
  
  데이터를 삽입한다고 하더라도 데이터의 주소를 연결해주기만 하여도 삽입이 완료되게 된다.

Types of linked lists

• (Basic) linked lists
  

• Doubly linked list: better accessibility
  
  앞 뒤로 데이터 참조가 쉽다.

• Doubly circular linked list
  
  맨 앞과 뒤도 가리키게 만들어 주는 방법도 존재하다.

Example 1: ArrayList vs. LinkedList

public class Lecture {

	// Sequential Add
	public static long add1(List<String> list) {
    
    // 현재 시간은 Milisecond 단위로 저장한다.
		long start = System.currentTimeMillis();
		for(int i=0; i<1000000; i++) list.add(i+"");
		long end = System.currentTimeMillis();
        
    // 작업 시간이 반환
		return end - start;
	}
    
    // Non-Sequential Add
    // 500 번째부터 x를 삽입하라
	public static long add2(List<String> list) {
		long start = System.currentTimeMillis();
		for(int i=0; i<10000; i++) list.add(500, "X");
		long end = System.currentTimeMillis();
		return end - start;
	}
    
    // 맨 마지막에서 부터 remove 실행
	public static long remove1(List<String> list) {
		long start = System.currentTimeMillis();
		for(int i=list.size()-1; i>=0; i--) list.remove(i);
		long end = System.currentTimeMillis();
		return end - start;
	}
    
    // 앞에서부터 remove 실행
	public static long remove2(List<String> list) {
		long start = System.currentTimeMillis();
		for(int i=0; i<10000; i++) list.remove(i);
		long end = System.currentTimeMillis();
		return end - start;
	}

	public static void main(String args[]) {
		ArrayList<String> al = new ArrayList<>(2000000);
		LinkedList<String> ll = new LinkedList<>();
		System.out.println("=== sequential add ===");
		System.out.println("ArraList : " + add1(al));
		System.out.println("LinkedList: " + add1(ll));
		System.out.println();
		System.out.println("=== non-sequential add ===");
		System.out.println("ArraList : " + add2(al));
		System.out.println("LinkedList: " + add2(ll));
		System.out.println();
		System.out.println("=== non-sequential delete ===");
		System.out.println("ArraList : " + remove2(al));
		System.out.println("LinkedList: " + remove2(ll));
		System.out.println();
		System.out.println("=== sequential delete ===");
		System.out.println("ArraList : " + remove1(al));
		System.out.println("LinkedList: " + remove1(ll));
	}
}

Example 2: ArrayList vs. LinkedList

public class Lecture {
	public static void main(String args[]) {
    //ArrayList는 따로 공간 할당
		ArrayList<String> al = new ArrayList<>(1000000);
		LinkedList<String> ll = new LinkedList<>();
		add(al);
		add(ll);
        //Access Time 측정
		System.out.println("=== access time ===");
		System.out.println("ArrayList : " + access(al));
		System.out.println("LinkedList: " + access(ll));
	}
    //List 객체는 superclass이기에 AL, LL 모두 삽입가능
	public static void add(List<String> list) {
		for(int i=0; i<100000; i++) list.add(i+"");
	}
    //list의 i번째 값을 가져오는 기능만 존재
	public static long access(List<String> list) {
		long start = System.currentTimeMillis();
		for(int i=0; i<10000; i++) list.get(i);
		long end = System.currentTimeMillis();
		return end - start;
	}
}

과연 어떤 것이 더 데이터 접근에 빠를까? 만약 중간쯤에 있는 데이터를 찾게 된다면 ArrayList는 데이터가 연속적으로 존재하기 때문에 어디쯤 위치에 있을것이라고 계산을 할 수 있다.(실재 Search 알고리즘이 존재한다.)

반면 LinkedList는 데이터 접근을 위해서 주소를 따라 계속해서 이동해야만 한다.

결론을 보아도 ArrayList가 참조를 하는 경우 좀더 유리한 것을 확인할 수 있다.

4. Stack and Queue

• Stack : LIFO(Last in Frist out) 방식으로 작동하는 자료 구조
  아무데나 데이터를 입력하고 삭제가 가능한 것이 아닌 먼저 넣은 데이터가 가장 나중에 나오는 방식의 자료구조이다.

  • 사용처 : 계산기, undo/redo, back/forward(web browser)
  • 사용법 : class Stack<E>

• Queue : FIFO(First in First out) 방식으로 작동하는 자료 구조
  먼저 넣은 데이터가 가장 먼저 나오는 방식의 자료구조이다.

  • 사용처 : printer queue, CPU scheduling, I/O buffers
  • 사용법 : interface Queue<E>
  • LinkedList가 Queue를 implement되어 있다.

Methods

Example: Stack vs. Queue

public class Lecture {
	public static void main(String[] args) {
    // Stack은 class라서 바로 사용
		Stack<String> st = new Stack<String>();
    // Queue는 interface이기에 LinkedList 를 사용
		Queue<String> q = new LinkedList<String>();
    
    // 스택에 데이터 삽입
		st.push("0");
		st.push("1");
		st.push("2");
        
    // 큐에 데이터 삽입
		q.offer("0");
		q.offer("1");
		q.offer("2");
        
		System.out.println("=== Stack ===");
		while(!st.empty()) System.out.println(st.pop());
        
		System.out.println("=== Queue ===");
		while(!q.isEmpty()) System.out.println(q.poll());
	}
}

Example: Implementing Stack

Stack의 함수들에는 다음이 존재한다.

• push, pop, peek, search

이 예제는 위의 함수들을 코드로 간단하게 구현해 본 부분이다.

import java.util.*;
public class MyStack<E> extends Vector<E> {
	// push는 데이터를 삽입하는 것이다.
	public E push(E item) {
		addElement(item); // defined in class Vector
		return item;
	}
    
    // pop은 가장 늦게 들어온 데이터를 빼내는 것이다.
	public E pop() {
		E e = peek();
		removeElementAt(size() - 1);
		return e;
	}
    
    // empty는 stack이 비어 있는지 확인하는 것이다.
	public boolean empty() {
		return size() == 0;
	}
    
    // peek는 가장 마지막 성분을 반환해 주는 것이다.
    public E peek() {
		int len = size();
		if( len == 0 ) throw new EmptyStackException();
		return elementAt(len - 1);
	}
    
    // 객체가 stack안에 있는지 확인하는 것이다.
	public int search(Object o) {
		int i = lastIndexOf(o);
		if(i >= 0) { return size() - i; }
		return -1;
	}
}

Example: Using Stack

이번에는 Stack을 가지고 무엇을 할 수 있을지 봐보자

public class Lecture {
	public static Stack<String> back = new Stack<>();
	public static Stack<String> forward = new Stack<>();
	public static void main(String[] args) {
		goURL("1. Google");
		goURL("2. Facebook");
		goURL("3. Naver");
		goURL("4. Daum");
		printStatus();
        goBack();
        
		System.out.println("=== After pushing 'back' ===");
		printStatus();
		goBack();

		System.out.println("=== After pushing 'back' ===");
		printStatus();
		goForward();
        
		System.out.println("=== After pushing 'forward' ===");
		printStatus();
		goURL("www.ABC.co.kr");
		System.out.println("=== After moving to a new URL ===");
		printStatus();
	}

// printStatue는 back과 forward state의 성분을 보는 것이다. 그리고 current page를 보는 것이다.
	public static void printStatus() {
		System.out.println("back:"+back);
		System.out.println("forward:"+forward);
		System.out.println("current page is " + back.peek() + ".");
		System.out.println();
	}
    
    // back에 모든 url을 넣고 forward는 비워준다.
	public static void goURL(String url) {
		back.push(url);
		if(!forward.empty()) forward.clear();
	}
    
    // forward에서 데이터를 빼내고 push에 데이터를 넣는다.
	public static void goForward() {
		if(!forward.empty()) back.push(forward.pop());
	}
    
    // back에서 데이터를 빼내고 push에 데이터를 넣는다.
	public static void goBack() {
		if(!back.empty()) forward.push(back.pop());
	}
}

Example: Using Queue

public class Lecture {
	// Queue의 선언
	static Queue<String> q = new LinkedList<String>();
	static final int MAX_SIZE = 5;

	public static void main(String[] args) {
		System.out.println("input 'help' to display help message.");
		while(true) {
			System.out.print(">>");
			try {
            //사용자에게 입력을 받음
				Scanner s = new Scanner(System.in);
                // 사용자에게 받은 입력 마지막에 있는 스페이스바를 없애줌
				String input = s.nextLine().trim();
                // 사용자 입력이 없다면 재 실행
				if("".equals(input)) continue;
                // q를 입력시 시스템 종료
				if(input.equalsIgnoreCase("q")) {
					System.exit(0);
                // help 입력시 내용을 출력
				} else if(input.equalsIgnoreCase("help")) {
					System.out.println(" help – displays help message.");
					System.out.println(" q or Q – exit the program.");
					System.out.println(" history – shows recent commands.");
				}
                // history 입력시 그동알 쳤던 입력들을 출력
            	else if(input.equalsIgnoreCase("history")) {
					int i=0;
					save(input);
					LinkedList<String> tmp = (LinkedList<String>)q;
					ListIterator<String> it = tmp.listIterator();
					while(it.hasNext()) System.out.println(++i+"."+it.next());
				} else {
					save(input);
					System.out.println(input);
				}
			} catch(Exception e) { System.out.println("input error."); }
		}
	}
    
    // 입력값들을 저장
	public static void save(String input) {
		if(!"".equals(input)) q.offer(input);
		if(q.size() > MAX_SIZE) q.remove();
	}
} 

여기에서 주의해야 하는 것이 하나 있는데, 만약에 Scanner을 닫아주지 않으면 에러가 발생한다. 그렇기 때문에 우리가 사용하지 않는 시점에서 Scanner을 닫아주도록 하자.

Priority Queue

element가 제거 될떄 priority에 따라서 데이터가 삭제 된다.

이러한 구조를 heap이라고 부른다. 그리고 이때 어떤것을 우선시 할지에 대한 기준을 넣어주어야 한다.

public class Lecture {
	public static void main(String[] args) {
		Queue<Integer> pq = new PriorityQueue<Integer>();
		pq.offer(3);
		pq.offer(1);
		pq.offer(5);
		pq.offer(2);
		pq.offer(4);
        
		System.out.println(pq);
		Integer i = null;
		while((i = pq.poll()) != null) System.out.println(i);
	}
}