[JAVA] LinkedList

- LinkedList 구조

• LinkedList는 ArrayList와 함께 List를 구현한 클래스로 Doubly-linked list 형태를 갖고 있다.  Doubly-linked는 양방향 구조로 각 노드가 앞, 뒤 노드를 참조하여 체인의 형태를 갖는다. LinkedList는 배열의 형태가 아니기 때문에 요소를 중간에 추가/삭제가 빈번할 때 유리하다. 하지만 첫 인덱스나 마지막 인덱스의 요소 추가/삭제는 ArrayList가 유리하다.

 

 

 

- LinkedList Constructors

• LinkedList()는 ArrayList와는 다르게 초기 용량을 설정 불가능하다. LinkedList는 노드를 이용하기 때문에 용량이 필요 없음.
• public LinkedList​(Collection <? extends E> c)는 매개변수로 받은 컬렉션에 있는 요소를 포함하는 LinkedList를 만든다.

 

- LinkedList Method

 

추가

 

 

- 첫 번째 메서드는 요소를 매개변수로 받아 가장 끝 노드(tail node)에 요소를 추가한다. 시간 복잡도는 O(1)이고 add()와 addLast()는 동등하다.

- 두 번째 메서드는 목록에 지정된 위치의 인덱스에 요소를 삽입한다. 시간 복잡도는 O(n)이다. 지정된 위치에 노드가 이미 있다면 연결된 노드를 끊고 다시 연결된다(노드가 하나씩 오른쪽으로 이동한다고 생각하자).

- 세 번째 메서드는 목록의 첫 부분에 지정된 요소를 추가한다.

 

제거

- 첫 번째 메서드는 매개변수로 인덱스를 받아 인덱스의 담긴 요소를 탐색하고 반환한 뒤 해당 요소 노드 연결을 해제한다. 시간 복잡도는 O(n)이다.

- 두 번째 메서드는 매개변수로 요소를 받아 지정된 요소를 탐색한 뒤 지정된 요소를 삭제하면 true를 반환한다. 지정된 요소로는 null 또한 가능하다. 시간 복잡도는 O(n)이다.

- removeFirst()는 첫 번째 노드를 removeLast()는 마지막 노드를 제거한다. 시간 복잡도는 O(1)이다.

 

검색

- contains(object o)는 지정된 요소를 list가 포함하고 있는지 boolean 타입으로 반환해 주는 메서드이다. 시간 복잡도는 O(n)이다.

- get(int index)는 지정된 인덱스를 list에서 찾아서 요소를 반환해 준다. 시간 복잡도는 O(n)이다.

- peek() 은 첫 번째 요소를 제거하지 않고 반환해준다. 만약 빈 list라면 null을 반환한다. element()는 빈 list에서'NoSuchElementException' 예외를 발생시킨다. 시간 복잡도는 O(1)이다.

- poll() 은 첫 번째 요소를 반환한 뒤 제거한다. 만약 빈 list라면 null을 반환한다.

 

- 소스코드

import java.util.LinkedList;


class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList(); // LinkedList 선언
        LinkedList<Integer> list1 = new LinkedList();
        list.add(3);               // 3
        list.addFirst(1);      // 1 3
        list.add(1, 2);     // 1 2 3
        list.add(4);                // 1 2 3 4
        list.add(5);                // 1 2 3 4 5

        list1.add(2);     // 2
        list1.add(3);     // 2 3

        System.out.println(list.peek());  // 1
        System.out.println(list.poll()); // 1을 반환한뒤 제거한다.
        System.out.println(list.peek());  // 2
        list.removeAll(list1);
        for (Integer I : list) {
            System.out.println(I);  // 4 5
        }
    }
}

출력

 

참고: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html

       https://st-lab.tistory.com/169

LinkedList (Java SE 11 & JDK 11 )