자바 LinkedList 구조 & 사용법

LinkedList 컬렉션

 

자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 다르게 구성되어있다.

ArrayList는 내부적으로 배열을 사용하지만, Linked List는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)하며 이어진다.

 

 

Linked List는 각 노드마다 다음 노드의 주소를 참조함으로서 연결 된다.

 

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};

 

---

 

Linked List 종류

 

• 단방향 연결 리스트(Single Linked List)
  
  위에서 보았듯이, 노드의 데이터와 다음 노드를 가리키기위한 포인터만 가지고 있는 링크드 리스트를 단방향 연결 리스트라고 한다. 
  Linked List의 Size가 1000개인 경우 999번 째 데이터에 접근하려면 참조를 999번 해야하기 때문에 비효율적인 경우가 발생한다.
• 양방향 연결 리스트(Doubly Linked List)
  참조를 앞뒤로 할 수 있기 때문에 각 노드에 대한 접근이 비교적 쉽다.

 

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    Node prev; // 이전 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};

 

실제로 Java의 컬렉션 프레임워크에 구현된 LinkedList 클래스는 Doubly linked list로 구현 되어 있다.

---

LinkedList 객체 생성

 

생성자	설명
LinkedList()	LinkedList객체를 생성
LinkedList(Collection c)	주어진 컬렉션을 포함하는 LinkedList객체를 생성

 

 

// int 타입만 삽입 가능
LinkedList<Integer> list = new LinkedList<>();

// 생성시 초기값 설정
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1, 2));

 

ArrayList와 달리, 초기 용적량을 지정하는 생성자는 없다. 

LinkedList는 데이터가 추가될 때마다 노드(객체)들이 생성되어 동적으로 추가되는 방식이다.

 

---

 

 

LinkedList 노드 추가 / 삽입

 

메서드	설명
void addFirst(Object o)	LinkedList의 맨 앞에 객체(o)를 추가
void addLast(Object o)	LinkedList의 맨 뒤에 객체(o)를 추가
boolean add(Object o)	LinkedList의 마지막에 객체를 추가 (성공시 true)
void add(int index, Object element)	지정된 위치(index)에 객체를 저장
void addAll(Collection c)	주어진 컬렉션의 모든 객체를 마지막 부분에 저장
void addAll(int index, Collection c)	지정한 위치부터 주어진 컬렉션의 데이터를 저장

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C", "D")));

list.addFirst("Fitst");

list.addLast("Last");

list.add(2, "Center");

 

addFirst()와 addLast()는 노드를 첫 번째, 마지막에 추가하는 것이기 때문에 O(1)의 복잡도가 걸리지만, 중간에 요소를 삽입하는 경우 중간 위치까지 순회하기 때문에 O(N)의 복잡도를 갖는다.

 

---

 

LinkedList 요소 삭제

 

메서드	설명
E removeFirst()	첫 번째 노드를 제거하고 제거된 요소를 반환
E removeLast()	마지막 노드를 제거하고 제거된 요소를 반환
E remove() E remove(int index)	첫 번 째 노드 / 위치(index)에 있는 노드를 제거하고 반환
boolean remove(Object o)	지정된 Object(obj)를 제거 (성공하면 true)
boolean removeAll(Collection c)	지정한 컬렉션에 저장된 것과 동일한 노드들을 LinkedList에서 제거
boolean retainAll(Collection c)	LinkedList에 저장된 객체 중에서 주어진 컬렉션과 공통된 것들만 남기고 제거
void clear()	LinkedList를 완전히 비운다.

 

 

removeFirst()와 remove() 메소드는 기능적으로 동일하다. 둘 다 LinkedList의 첫 번째 요소를 제거하고 반환한다.

차이점은 removeFirst()은  Deque 인터페이스에서 정의된 메소드이며, remove()는 Collection 인터페이스에서 정의된 메소드이다.

 

---

 

LinkedList vs ArrayList 성능 비교

연산	LinkedList (Doubly)	ArrayList
첫 번째 위치에 insert / remove	O(1)	O(N)
마지막 위치에 insert / remove	O(1)	O(1) / O(N)
중간에 insert / remove	O(N) / 검색 시간 + O(1)	O(1) / O(N)
값으로 search	O(N)	O(N)
인덱스로 값 search	O(N)	O(1)
값으로 remove	O(N)	O(N)

 

ArrayList의 첫 번째 위치에 insert / remove의 복잡도가 O(N)인 이유는 그 이후 요소를 당기거나 밀어야하기 때문이다.

ArrayList의 마지막 위치에 insert / remove의 복잡도가 O(N)이 될 수 있는 이유는 배열이 꽉차서 복사가 일어나야 하는 경우 때문이다.

 

LinkedList의 내부 메소드 중 지정된 위치(index)에서 노드를 제거하고 삭제와 같은 모든 index 접근에서 노드의 중간이 되는 지점보다 앞에 있다면 정방향 순회를, 중간보다 뒤에 있다면 역방향 순회를 한다.
따라서 LinkedList가 순회에 걸리는 비교적 정확한 시간은 O(N/2)가 된다. 

- index위치 노드 접근 관련 메소드
get(int index): 특정 인덱스의 요소를 반환하는 메소드.
set(int index, E element): 특정 인덱스의 요소를 다른 값으로 대체하는 메소드.
add(int index, E element): 특정 인덱스에 새로운 요소를 삽입하는 메소드.
remove(int index): 특정 인덱스의 요소를 제거하는 메소드.

 

아래는 java.util.LinkedList에서 사용되는 실제 코드이다.

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) { //노드의 중간 위치를 보고 판단
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

---

 

LinkedList 노드 검색

 

메서드	설명
int size()	LinkedList에 저장된 객체의 개수를 반환
boolean isEmpty()	LinkedList가 비어있는지 확인
boolean contains(Object o)	지정된 객체(obj)가 LinkedList에 포함되어 있는지 확인
boolean containsAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되었는지 알려준다.
int indexOf(Object o)	지정된 객체(obj)가 저장된 위치를 찾아 반환한다.
int lastIndexOf(Object o)	지정된 객체(obj)가 저장된 위치를 역방향으로 찾아 반환한다.

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// 해당 값을 가지고 있는 요소 위치를 반환 (앞에서 부터 검색) 
list1.indexOf("B"); // 1

// 해당 값을 가지고 있는 요소 위치를 반환 (뒤에서 부터 검색) 
list1.lastIndexOf("D"); // -1 : 찾고자 하는 값이 없으면


LinkedList list1 = new LinkedList();
list1.add("1");
list1.add("2");

// list1안에 "1" 값이 있는지 확인
list1.contains("1"); // true


LinkedList list2 = new LinkedList();
list2.add("1");
list2.add("2");
 
// list1에 list2의 모든 노드가 포함되어 있는지 확인
list1.containsAll(list2); // true

 

---

 

LinkedList 노드 얻기

 

LinkedList는 ArrayList와 달리 중간에 위치하는 노드에 접근하려는 경우 참조를 따라 일일이 이동해야해서 탐색 성능을 ArrayList보다는 좋지 않다.

 

메서드	설명
E get(int index)	지정된 위치(index)에 저장된 객체를 반환
List subList(int fromIndex, int toIndex)	fromIndex <= x < toIndex에 존재하는 x노드들의 객체들을 List로 반환한다.

 

---

 

LinkedList 노드 변경

메서드	설명
E set(int index, E element)	지정한 위치(index)에 있는 노드의 값을 element로 변경하고, 변경되기 전의 값을 반환한다.

 

---

 

LinkedList 배열 변환

 

LinkedList는 배열은 아니지만, List Collection이기 때문에 연속된 값으로서 배열로 변환이 가능하다.

 

메서드	설명
Object[] toArray()	LinkedList에 저장된 모든 객체들을 객체 배열로 반환한다.
Object[] toArray(Object[] objArr)	LinkedList에 저장된 모든 객체들을 객체배열 objArr에 담아 반환한다.

 

LinkedList<Number> list1 = new LinkedList<>();
list1.add(1);
list1.add(2);

Object[] tmp = {0, 1, 2, 3, 4, 5}; // 통째로 추가할 배열

Number[] arr = (Number[]) list1.toArray(tmp);
System.out.println(Arrays.toString(arr)); // [1, 2, null, 3, 4, 5]

 

list1의 size 크기가 tmp의 size크기보다 작아서 return된 arr값을 출력해보면 null값이 들어간 것을 확인할 수 있다.

index 끝에 null을 삽입하여 배열의 끝임을 알 수 있도록 한다.

 

---

 

LinkedList 순회 (이터레이터)

 

메서드	설명
Iterator iterator()	LinkedList의 Iterator객체를 반환
ListIterator listIterator()	LinkedList의 ListIterator를 반환
ListIterator listIterator(int index)	LinkedList의 지정된 위치부터 시작하는 ListIterator를 반환한다.

 

LinkedList는 Iterator 뿐만 아니라 ListIterator도 지원한다.

Iterator는 Collection 인터페이스를 구현한 컬렉션에서 모두 사용할수 있는 반면, ListIterator는 오로지 List 컬렉션에서만 사용이 가능하다.

 

Iterator는 컬렉션의 요소에 접근할 때 단 방향으로만 순회하는 반면, ListIterator 인터페이스는 컬렉션 요소의 대체, 추가 그리고 인덱스 검색 등을 위한 작업에서 양방향으로 이동하는 것을 지원한다.

 

ListIterator it = list.listIterator(); 
 
while(it.hasNext()) {
	System.out.print(it.next());
}

while(it.hasPrevious()) {
	System.out.print(it.previous());
}

 

 

---

 

LinkedList 스택 & 큐

 

LinkedList는 리스트 용도로서 뿐만 아니라, 구조 특성상 Stack이나 Queue 로서도 이용이 가능하다.

 

메서드	설명
Object element()	LinkedList의 첫 번째 노드를 반환
boolean offer(E e)	지정된 노드(e)를 LinkedList의 끝에 추가 성공 시 true / 실패 시 false
E peek()	LinkedList의 첫 번째 노드를 반환
E poll()	LinkedList의 첫 번째 노드를 반환 LinkedList의 요소에서 제거된다.
void push(E e)	맨 앞에 노드(e)를 추가 (addFirst와 동일)
Iterator descendingIterator()	역순으로 조회하기 위한 descendingIterator를 반환
E getFirst() E getLast(0	LinkedList의 첫 번째 / 마지막 노드를 반환
boolean offerFirst(E e) boolean offerLast(E e)	지정된 노드(e)를 LinkedList의 맨 앞 / 뒤에 추가 성공 시 true / 실패 시 false
E peekFirst() E peekLast()	첫 번째 / 마지막 노드를 반환
E pollFirst() E pollLast()	첫 번째 / 마지막 노드를 반환하면서 제거
E pop()	첫 번째 노드를 제거 (removeFirst와 동일)
boolean removeFirstOccurrence(Object o)	첫 번째로 일치하는 객체를 제거
boolean removeLastOccurrence(Object o)	역순으로 순회하며 첫 번째로 일치하는 객체를 제거

 

---

 

LinkedList 동기화 처리

 

멀티 쓰레드 환경에서는 컬렉션에 동시 접근에 문제가 발생하는 것을 방지하기 위해 동기화 처리된 리스트를 반환받아 사용할 수 있다.

 

/* ArrayList 동기화 처리 */
List<String> l1 = Collections.synchronizedList(new ArrayList<>());

/* LinkedList 동기화 처리 */
List<String> l2 = Collections.synchronizedList(new LinkedList<>());