[Java] 컬렉션(Collection) - 2. List(LinkedList), Stack, Queue

LinkedList

- ArrayList가 배열을 이용해서 발생할 수 있는 성능적인 단점을 보완하고자 고안되었다.

- 내부는 이중 연결 리스트로 구현 되어 있다.

단일 연결 리스트
- 저장한 요소가 순서를 유지하지 않고 저장되지만 이러한 요소들 사이를 링크로 연결하여 구성하며 마치 연결된 리스트 형태인 것 처럼 만든 자료구조이다.
요소의 저장과 삭제 시 다음 요소를 가리키는 참조 링크만 변경하면 되기 때문에 요소의 저장과 삭제가 빈번히 일어나는 경우 ArrayList보다 성능면에서 우수하다.
하지만 단일 연결 리스트는 다음 요소만 링크하기 때문에 이전 요소로 접근하기 어렵다. 이를 보완하고자 나온 것이 이중 연결 리스트이다.

이중 연결 리스트
- 단일 연결 리스트는 다음 요소만 링크하는 반면 이중 연결 리스트는 이전 요소도 링크하여 이전 요소로 접근하기 쉽게 고안된 자료구조이다.
하지만 내부적으로 요소를 저장하는 방법에 차이가 있다.
각 컬렉션 프레임워크 클래스들의 특징을 파악하고 그에 따라 적합한 자료구조를 구현한 클래스를 선택하는 것이 좋다.

 

LinkedList 인스턴스 생성

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

 

요소를 추가할 때는 add를 이용한다.

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

 

저장된 요소의 갯수는 size() 메소드를 이용한다.

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

 

for문과 size()를 이용해서 반복문을 활용할 수도 있다.

요소를 꺼내올 때는 get()을 사용하며, 인자로 전달하는 정수는 인덱스처럼 사용하면 된다.

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

출력값=>
0 : apple
1 : banana
2 : orange
3 : mago
4 : grape

 

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

향상된 for문도 사용 가능하다.

		linkedList.remove(1);
	
		for(String s : linkedList) {
			System.out.println(s);
		}

출력값=>
apple
orange
mago
grape

 

set() 메소드 이용해서 요소를 수정했다.

toString() 메소드가 오버라이딩 되어 있어서 모든 요소 정보를 쉽게 볼 수 있다.

isEmpty() 메소드를 이용해서 list가 비어있는지 확인할 수 있다.

리스트 내 요소를 모두 제거하는 clear() 메소드를 이용할 수 있다.

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

출력값=>
[pineapple, orange, mago, grape]
false
true

---

Stack

- Stack은 리스트 계열 클래스의 Vector 클래스를 상속 받아 구현하였다.

- 스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하며 후입선출(LIFO - Last input First Out) 방식의 자료구조라 부른다.

- 저장 순서 유지X, 중복 인스턴스 저장X (null값도 중복되지 않게 하나의 null만 저장)

 

Stack인스턴스 생성

		Stack<Integer> integerStack = new Stack<>();

 

Stack에 값 넣을 때는 push() 메소드를 이용한다.

add()도 이용 가능하지만 Vector의 메소드이므로 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));	//1

 

stack에서 값을 꺼내는 메소드

- peek() : 해당 스택의 가장 마지막(상단)에 있는 요소 반환

- pop() : 해당 스택의 가장 마지막(상단)에 있는 요소 반환 후 제거

		System.out.println("peek() : " + integerStack.peek());
		System.out.println(integerStack);
		
		System.out.println("pop() : " + integerStack.pop());
		System.out.println(integerStack);

출력값=>
peek() : 5
[1, 2, 3, 4, 5]
pop() : 5
[1, 2, 3, 4]

 

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());	//EmptyStackException 발생

출력값=>
pop() : 4
pop() : 3
pop() : 2
pop() : 1

---

Queue

- Queue는 선형 메모리 공간에 데이터를 저장하는 선입선출(FIFO - First Input First Out) 방식의 자료구조이다.

- Queue 인터페이스를 상속 받는 하위 인터페이스들은 Deque, BlockingQueue, TransferQuere 등 다양하지만

  대부분의 큐는 LinkedList를 이용한다.

 

Queue자체로 인터페이스이기 때문에 인스턴스 생성이 불가하다.

		//Queue<String> 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);

출력값=>
peek() : first
[first, second, third, fourth, fifth]
poll() : first
[second, third, fourth, fifth]