java Collection12 -list3,4

LinkedList

LinkedList	ArrayList가 배열을 이용해서 발생할 수 있는 성능적인 단점을 보완하고자 고안 되었다.  * 내부는 이중 연결 리스트로 구현 되어 있다.
단일 연결 리스트	저장한 요소가 순서를 유지하지 않고 저장 되지만 이러한 요소들 사이를 링크로 연결하여 구성하며  *    마치 연결 된 리스트 형태인 것처럼 만든 자료 구조이다.  *    요소의 저장과 삭제 시 다음 요소를 가리키는 참조 링크만 변경하면 되기 때문에  *    요소의 저장과 삭제가 빈번히 일어나는 경우 ArrayList보다 성능 면에서 우수하다. 하지만 단일연결 리스트는 다음 요소만 링크하기 때문에 이전 요소로 접근하기 어렵다.  *    이를 보완하고자 만든 것이 이중 연결 리스트이다.
이중 연결 리스트	: 단일 연결 리스트는 다음 요소만 링크하는 반면 이중 연결 리스트는 이전 요소도 링크하여  *    이전 요소로 접근하기 쉽게 고안 된 자료 구조이다.  *      * 하지만 내부적으로 요소를 저장하는 방법에는 차이가 있는 것이다.  * 각 컬렉션 프레임워크 클래스들의 특징을 파악하고 그에 따라 적합한 자료 구조를 구현할 클래스를 선택하는 것이 좋다.

---

/* LinkedList 인스턴스 생성 */

		List<String> linkedList = new LinkedList<>();

/* 요소를 추가할 때는 add를 이용한다. */ /* 저장된 요소의 갯수는 size() 메소드를 이용한다. */

		linkedList.add("apple");
		linkedList.add("banana");
		linkedList.add("orange");
		linkedList.add("grape");

		System.out.println(linkedList.size());

4

---

/* for문과 size()를 이용해서 반복문을 사용할 수도 있다.  * 요소를 꺼내올 때는 get()을 사용하며, 인자로 전달되는 정수는 인덱스처럼 사용하면 된다. */

		for(int i = 0; i < linkedList.size(); i++) {
			System.out.println(linkedList.get(i));
		}

apple

banana

orange

grape

---

/* 요소를 제거할 때는 remove() 메소드를 이용하며 인덱스를 활용한다. */

		linkedList.remove(1);

apple

orange

grape

---

/* for-each 문도 사용 가능하다. */

		for(String str : linkedList) {
			System.out.println(str);
		}

apple

orange

grape

---

/* set() 메소드를 이용해서 요소를 수정할 수도 있다. pineapple로 바뀜 */  toString() 메소드가 오버라이딩 되어 있어서 모든 요소의 정보를 쉽게 볼 수 있다. */ 리스트 내 요소를 모두 제거하는 clear() 메소드를 사용할 수도 있다. *

		linkedList.set(0, "pineapple");
		
		System.out.println(linkedList);
		
		System.out.println(linkedList.isEmpty());
		
		linkedList.clear();
		
		System.out.println(linkedList.isEmpty());

 

[pineapple, orange, grape]

false

true

---

Stack

Stack은 리스트 계열의 클래스 Vector 클래스를 상속 받아 구현하였다. 스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하며 후입 선출(LIFO - Last In First Out) 방식의 자료구조라 부른다.

		/* Stack 인스턴스 생성 */
		Stack<Integer> integerStack = new Stack<>();

---

stack에 값을 넣을 때는 push() 메소드를 사용한다. add()도 사용 가능하지만 Stack의 기능이므로 push()를 사용하는 것이 좋다.

		integerStack.push(1);
		integerStack.push(2);
		integerStack.push(3);
		integerStack.push(4);
		integerStack.push(5);
		
		System.out.println(integerStack);

[1, 2, 3, 4, 5]

---

/* 스택에서 요소를 찾을 때 search()를 이용할 수 있다. * 인덱스가 아닌 위에서부터의 순번을 의미하며 가장 상단의 위치가 0이 아닌 1부터 시작한다. */

		System.out.println(integerStack.search(5));
		System.out.println(integerStack.search(1));

1

5

---

스택에서 값을 꺼내는 메소드는 크게 2가지로 볼 수 있다.
peek()	해당 스택의 가장 마지막에(상단에 있는) 요소 반환
pop()	해당 스택의 가장 마지막에(상단에 있는) 요소 반환 후 제거

		System.out.println("peek() : " + integerStack.peek());
		System.out.println(integerStack);
		
		System.out.println("pop() : " + integerStack.pop());
		System.out.println(integerStack);
		
		/* pop()은 꺼내면서 요소를 제거하기 때문에 스택이 비어있는 경우 에러가 발생할 수 있다. */
		System.out.println("pop() : " + integerStack.pop());
		System.out.println("pop() : " + integerStack.pop());
		System.out.println("pop() : " + integerStack.pop());
		System.out.println("pop() : " + integerStack.pop());
//System.out.println("pop() : " + integerStack.pop()); //java.util.EmptyStackException 발생

POP,PEEK

peek() : 5

[1, 2, 3, 4, 5]

pop() : 5

[1, 2, 3, 4]

POP 스택이 비어있는 경우

pop() : 4
pop() : 3
pop() : 2
pop() : 1

---

Queue	Queue는 선형 메모리 공간에 데이터를 저장하는 선입 선출(FIFO - First Input First Out) 방식의 자료구조이다.  * Queue 인터페이스를 상속 받는 하위 인터페이스들은  Deque, BlockingQueue, TransferQueue 등 다양하지만  * 대부분의 큐는 LinkedList를 이용한다. Queue 자체로는 인터페이스이기 때문에 인스턴스 생성이 불가능하다.   Queue<String> que = new Queue<>();
Queue 자체로는 인터페이스이기 때문에 인스턴스 생성이 불가능하다. */ Queue que = new Queue<>();

---

LinkedList로 인스턴스 생성

		Queue<String> que = new LinkedList<>();

---

큐에 데이터를 넣을 때에는 offer()를 사용한다.

		que.offer("first");
		que.offer("second");
		que.offer("third");
		que.offer("fourth");
		que.offer("fifth");
        System.out.println(que);

[first, second, third, fourth, fifth]

---

큐에서 데이터를 꺼낼 때는 2가지 메소드가 있다
peek()	해당 큐의 가장 앞에 있는 요소(먼저 들어온 요소)를 반환
poll()	해당 큐의 가장 앞에 있는 요소(먼저 들어온 요소)를 반환하고 제거

		System.out.println("peek() : " + que.peek());
		System.out.println(que);
		
		System.out.println("poll() : " + que.poll());
		System.out.println(que);
		
		System.out.println("poll() : " + que.poll());
		System.out.println("poll() : " + que.poll());
		System.out.println("poll() : " + que.poll());
		System.out.println("poll() : " + que.poll());
		System.out.println("poll() : " + que.poll()); //반환 값이 없을 경우 null로 반환

peek() : first

[first, second, third, fourth, fifth]

poll() : first

[second, third, fourth, fifth]

poll() : second

poll() : third

poll() : fourth

poll() : fifth

poll() : null

---