[Java] LinkedList - 컬렉션 프레임워크

들어가면서

ArrayList는 내부에 배열을 활용하여 리스트를 구현하는 자료구조였다.

따라서 ArrayList는 배열이 갖고 있는 단점을 그대로 갖고 있다.

• 크기를 동적으로 변경할 수 없다
• 데이터의 삭제 / 삽입시에 성능이 좋지 않다

노드와 연결

딱 필요한 만큼만 크기를 갖고, 데이터를 중간에 삭제 / 삽입할 때 효율적인 자료구조가 존재한다

바로 노드를 만들어서 서로 연결하는 방식이다

 

노드 클래스

public class Node{
	Object item;
	Node next;
}

 

노드에 데이터 추가

 

 

• Node 인스턴스는 item와 next를 저장하고 있다.
• item은 데이터를 의미하고, next는 다음 노드의 참조값을 저장하게 된다
• 따라서 Node1의 참조값을 Node0의 next가 저장하고 있다면 두 노드가 연결된 것 처럼 보이게 된다

노드 이어가기

여러 노드를 선언하고 이어가는 방법은 다음과 같다

Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");

 

이어진 노드들을 순회

노드들을 모두 순회하는 방법은 다음과 같게 된다

Node x = first;
while (x != null) {
	System.out.println("x.item = " + x.item);
    x = x.next;
}

 

이런 노드를 기반으로 만들어낸 자료구조를 연결 리스트 , LinkedList 라고 한다

다만 위에서는 한 방향으로만 노드를 이어줄 수 있었는데, 자바에서 제공하는 컬렉션 프레임워크의 LinkedList의 경우에는 본인의 앞, 뒤 노드에 대한 참조값을 모두 저장하고 있어서 양방향으로 이동할 수 있다. 이를 양방향 연결 리스트라고 한다

 

LinkedList 기능

ArrayList와 같이 List 자료구조를 구현하고 있기 때문에 기본적으로 제공하는 기능은 동일하다.

다만 LinkedList는 스택 혹은 큐로 활용할 수 있도록 추가적으로 제공하는 메서드가 존재한다.

기본 메서드

 생성 및 선언

• 제네릭 타입을 지정하여 기본으로 빈 리스트를 생성
• 인자로 컬렉션을 넘겨주어 해당 값을 저장하고 있는 리스트 생성

LinkedList<Integer> linkedList1 = new LinkedList<>();
LinkedList<Integer> linkedList2 = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> linkedList3 = new LinkedList<>(linkedList2);

 

요소 추가

• 리스트의 가장 앞에 요소 추가
• 리스트의 가장 뒤에 요소 추가
• 리스트의 가장 앞에 요소 추가
• 인덱스를 지정하여 해당 인덱스 위치에 요소 삽입

linkedList3.addFirst(0);
linkedList3.addLast(4);
linkedList3.add(6);
linkedList3.add(5, 5);

 

여러 요소 추가

• 특정 컬렉션에 존재하는 값을 기존 리스트의 뒤에 이어서 저장
• 특정 컬렉션에 존재하는 값을 특정 인덱스부터 이어서 저장

linkedList1.addAll(linkedList3);
linkedList2.addAll(1, linkedList1);

 

요소 삭제

• 리스트의 가장 앞 원소 삭제
• 특정 객체의 값을 찾아서 삭제
• 특정 인덱스의 원소 삭제
• 마지막 원소 삭제

linkedList3.remove();
linkedList3.remove((Integer) 4);
linkedList3.remove(2);
linkedList3.removeLast();

 

여러 요소 삭제

• 특정 컬렉션에 존재하는 값을 찾아서 모두 삭제
• 특정 컬렉션에 존재하는 값을 제외한 모든 값 삭제

linkedList3.removeAll(Arrays.asList(1, 2));
linkedList2.retainAll(Arrays.asList(2, 3));

 

요소 검색

• 리스트의 크기 반환
• 리스트가 비어있는 리스트인지 여부 반환
• 리스트가 특정 데이터를 포함하고 있는지 반환
• 리스트에서 특정 객체의 인덱스를 찾아서 반환, 없다면 - 1 반환

system.out.println("linkedList3.size() = " + linkedList2.size())
System.out.println("linkedList3.isEmpty() = " + linkedList2.isEmpty());
System.out.println("linkedList3.contains(4) = " + linkedList2.contains(4));
System.out.println("linkedList3.indexOf(3) = " + linkedList2.indexOf(3));

요소 얻기

• 특정 인덱스의 요소 얻기
• 서브 리스트로 만들어서 반환받기

System.out.println("linkedList3.get(2) = " + linkedList2.get(2));
System.out.println("linkedList3.subList(2,3) = " + linkedList2.subList(0, 3));

요소 변경

• 특정 인덱스의 요소 변경하기

linkedList2.set(linkedList2.size() - 1, 1);

 

스택과 큐 지원 메서드

• offer : add 와 동일하지만 예외처리 부분에서 차이가 있다.
• push : addFirst와 동일하다
• peek : 리스트의 가장 앞 요소 반환
• poll : 리스트의 가장 앞 요소 제거 후 반환 ( 빈 리스트이면 null 반환 )
• pop : 리스트의 가장 앞 요소 제거 후 반환 ( 빈 리스트이면 예외 발생

linkedList2.offer(1);
linkedList2.push(5);
System.out.println("linkedList2.peek() = " + linkedList2.peek());
System.out.println("linkedList2.poll() = " + linkedList2.poll());
System.out.println("linkedList.pop() " + linkedList2.pop());