[java] LinkedList 까먹어서 다시 정리함

LinkedList란?

Java에서 LinkedList는 기본적으로 Doubly Linked List임 (이중 연결 리스트)

List는 Singly Linked List와 Doubly Linked List가 있는데, 단일 연결 리스트에서는 다음은 O(1)만에 찾을 수 있지만 이전은 처음부터 탐색해야함. 그래서 나온게 Doubly Linked List. 이전 노드 정보까지 같이 가지고 있음.

 

 

 

 

item이 앞뒤로 연결되어있어서 O(1)만에 찾을 수 있음.

 

LinkeList 자체에서

int size;
Node<E> first;
Node<E> last;

를 관리하고 있으므로 first, last도 O(1)만에 찾을 수 있음. 나머지는 ListItr가 순회하면서 찾음. O(n)

 

List의 구현체에는 LinkedList, ArrayList 등이 있음.

 

addFirst() 인경우

ArrayList에서는 O(n)임. 

- 첫번째에 item을 넣고 나머지를 한칸씩 옮겨줘야해서 n만큼의 시간이 듦.

LinkeList에서는 O(1)임.

- 첫번째 item을 넣고 링크만 연결해주면 됨.

 

addLast()인경우

ArrayList와 LinkedList 모두 O(1)임. (왠지알지?)

 

중간에 넣는 경우 

ArrayList에서는 O(n)임.

- 마찬가지로 한칸씩 옮겨줘야하니까.

LinkList에서는 O(1)임.

- 마찬가지로 새로운 item(node)를 만들고 링크만 연결해주면됨.

 

근데 여기서 조건은, 중간 위치를 안다는 전제 하에 O(1)임.

 

만약, 어딘지 모른다면 탐색 하는시간 O(n) + 새로운 item 링크연결 O(1)임.

장점은 위치만안다면, O(1)이라는 것임.

 

예를들어, 특정 위치에서 계속 node를 추가해야한다면,

ArrayList에서는 계속 node를 뒤로 밀어줘야함. O(1) + O(n)임.

LinkedList에서는 아무리 해도 O(1) + O(1)임.

 

그 특정 위치를 어떻게 아냐? 아래 나옴.

 

하지만 잘 쓰진 않음!

왜냐면 들고있는 정보가 많아서 메모리를 많이먹음!

오히려 java에서는 ArrayList 나 ArrayDeque 을 많이 씀.

 

필요한 경우는?

텍스트 커서를 구현하는 경우

- 앞뒤를 알면 빠르게 수정삭제할수있음 O(1) 

- 물론 실제론 LinkedList로 구현하진 않고 버퍼등을 사용함

 

플레이리스트에서 특정 위치 다음에 계속 새 곡을 삽입하는 경우

- 위치만 알면 추가는 O(1)

 

순회하면서 삭제하는 경우

- 짝수만 삭제한다면? 한번에 순회하면서 삭제할 수 있음 O(n). 매번 자리 이동할 필요 없음. O(n) + O(n) + ...

 

LRU(Least Recently Used) 캐시

최근에 B가 다시 사용되었다면 B를 떼어내서 제일 마지막에 붙이는 작업을 O(1)만에 할 수 있음.

근데 찾으려면 순회해야하잖아? 그래서 HasMap을 같이 사용함

A를 B라고 보시길...

 

왜 ArrayList를 사용 안하냐?

B를 제일뒤에 갖다 붙이면 나머지 것들을 전부 앞으로 옮겨야함. O(n)

 

결국 어떤 상황에서 LinkedList가 강할까?

1. 현재 노드의 위치를 이미 알고 있다.
2. 그 위치에서 삽입·삭제가 빈번하게 발생한다.
3. 인덱스 기반 랜덤 접근은 거의 필요 없다.
4. 노드당 추가 메모리 사용을 감수할 수 있다.

    

구현과 추상화

LinkedList는 List, Deque를 구현함.

 

 

Queue를 구현한 Deque 는 양쪽에서 들어가고 나갈 수 있음.

 

interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);

    E removeFirst();
    E removeLast();

    E getFirst();
    E getLast();

    // 그 외 여러 메서드
}

 

Deque에서는 index 정보를 들고있지 않음. ListIterator로 next를 찾으며 순회함.

class ListItr {
    Node<E> next;       // 다음에 반환할 노드
    Node<E> lastReturned; // 직전에 반환한 노드
    int nextIndex;      // 다음 노드의 인덱스
}

 

ListItr는 직전에 반환한 노드를 기억하고 있기 때문에, 위에서 말한 찾은 위치만 안다면! O(1)로 추가할 수 있다는 장점이 있음.

 

 

List는 왜 받았냐?

중간에 수정하려면 get, set, add, remove, index등이 필요함.

예를들어 아래와 같은 코드가 필요함. 그래서 받음.

add(2, X)

 

 

그치만 LinkedList에서 index는 바로 2를 찾아온다는게 아님. get(2)라는건 iterator로 순환해서 2위치의 것을 찾아온다는 의미임. 따라서 O(n)임. 그래서 LRU에서는 HashMap을 쓰는 것.

 

 

 

끝.