Java :: Collection :: 1.3 LinkedList

Java의 정석 3판을 보며 공부한 내용을 정리하였습니다.
남궁성님께 많이 배우고 있습니다.

1.3 LinkedList

# 배열의 장점

• 간단한 구조
• 쉽게 사용 가능
• 데이터를 읽는 데 걸리는 시간이 빠르다.

# 배열의 단점

• 크기 변경 불가능
• 비순차적인 데이터의 추가 및 삭제에 시간이 많이 걸린다.

# 링크드리스트

이런 단점을 보완하는 자료구조가 바로 !! 링크드 리스트(Linked list)!!!

그림 1. 배열과 링크드 리스트

위 그림과 같이 링크드 리스트는 각 노드(node)가 자신과 연결될 다음 노드의 주소값과 데이터를 갖는다.

class Node{
	Node	next;	// 다음 노드의 주소
    Object	obj;	// 데이터

# 링크드 리스트의 데이터 추가

그림 2. 링크드 리스트에서의 데이터 추가

예를 들어 다음과 같이 노드가 있다고 해보자.

A-> B-> C-> D-> E

A는 B의 주소를 갖고 있고, B는 C, C는 D, ...

만약 여기서 F를 B와 C사이에 넣고 싶다면!

A-> B-> F-> C-> D-> E

위와 같이 B가 다음 노드로 F의 주소를 갖고
F는 C의 주소를 가지면 된다.
그럼 삭제는 어떻게 할까 ?

# 링크드 리스트의 데이터 삭제

그림 3. 링크드 리스트에서의 데이터 삭제

마찬가지로 앞에 연결했던 노드에 뒤 노드의 주소를 저장해서 이어주면 된다.

---

더블 링크드 리스트(이중 연결리스트; doubly linked list)

링크드 리스트가 단방향인데 그러면 양쪽으로 연결하면 어떨까?

그림 4. 더블 링크드 리스트(doubly linked list)

그게 바로 더블 링크드 리스트(이중 연결리스트; doubly linked list)이다.

class Node{
	Node	next;		// 다음 노드의 주소
    Node	previous;	// 이전 노드의 주소
    Object	obj;		// 데이터

링크드 리스트에서 이전 노드의 추소만 추가된 것이다.

---

더블 써큘러 링크드 리스트(이중 원형 연결리스트; doubly circular linked list)

여기서 한 발짝 더 나아간다면?

A - B - C - D - E - A

이렇게 순환 구조로는 어떻게 하면 될까?
가장 마지막 노드(E)에 다음 노드 주소값으로 A를 넣어주면 된다.
마찬가지로 첫 노드(A)에 이전 노드 주소값으로 E를 넣으면 순환 구조가 된다.

이 자료구조는 더블 써큘러 링크드 리스트(이중 원형 연결리스트; doubly circular linked list)이다.

---

LinkedList의 생성자와 메서드

• LinkdList()
  -> LinkedList 객체 생성
• LinkedList(Collection c)
  -> 주어진 컬렉션을 포함하는 LinkedList 객체 생성
• boolean add(Object o)
  -> 지정된 객체(o)를 LinkedList의 끝에 추가. 저장 성공 시 true, 실패하면 false
• void add(int index, Object element)
  -> 지정된 위치(index)에 객체(element) 추가
• boolean addAll(Collection c)
  -> 주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가. 성공 시 true, 실패 시 false
• boolean addAll(int index, Collection c)
  -> 지정된 위치(index)에 주어진 컬렉션에 포함된 모든 요소를 추가. 성공 시 true, 실패 시 false
• void clear()
  -> LinkedList 의 모든 요소 삭제
• boolean contains(Object o)
  -> 지정된 객체가 LinkedList에 포함되었는지 알려줌
• boolean containsAll(Collection c)
  -> 지정된 컬렉션의 모든 요소가 포함되었는지 알려줌
• Object get(int index)
  -> 지정된 위치(index)의 객체를 반환
• int indexOf(Object o)
  -> 지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환
• boolean isEmpty()
  -> LinkedList가 비어있는지 알려줌. 비어있으면 true
• Iterator iterator()
  -> Iterator를 반환
• int lastIndexOf(Object o)
  -> 지정된 객체의 위치(index)를 반환(끝부터 역순검색)
• ListIterator listIterator()
  -> ListIterator를 반환
• ListIterator listIterator(int dex)
  -> 지정된 위치에서부터 시작하는 ListIterator를 반환
• Object remove(int index)
  -> 지정된 위치(index)의 객체를 LinkedList에서 제거
• boolean remove(Object o)
  -> 지정된 객체를 LinkedList에서 제거. 성공하면 true, 실패하면 false
• boolean removeAll(Collection c)
  -> 지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
• boolean retainAll(Collection c)
  -> 지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
• Object set(int index, Object element)
  -> 지정된 위치(index)의 객체를 주어진 객체로 바꿈
• int size()
  -> LinkedList에 저장된 객체의 수 반환
• List subList(int fromIndex, int toIndex)
  -> LinkedList의 일부를 List로 반환
• Object[] toArray()
  -> LinkedList에 저장된 객체를 배열로 반환
• Object[] toArray(Object[] a)
  -> LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환
• Object element()
  -> LinkedList의 첫 번째 요소 반환
• boolean offer(Object o)
  -> 지정된 객체(o)를 LinkedList의 끝에 추가. 성공하면 true, 실패하면 false
• Object peek()
  -> LinkedList의 첫 번째 요소를 반환
• Object poll()
  -> LinkedList의 첫 번째 요소를 반환. LinkedList에서는 제거됨
• Object remove()
  -> LinkedList의 첫 번째 요소를 제거
• void addFirst(Object o)
  -> LinkedList의 맨 앞에 객체(o)를 추가
• void addLast(Object o)
  -> LinkedList의 맨 끝에 객체(o)를 추가
• Iterator descendingIterator()
  -> 역순으로 조회하기 위한 DescendingIterator 반환
• Object getFirst()
  ->LinkedList의 첫 번째 요소 반환
• Object getLast()
  -> LinkedList의 마지막 요소 반환
• boolean offerFirst(Object o)
  -> LinkedList의 맨 앞에 객체(o)를 추가. 성공하면 true
• boolean offerLast(Object o)
  -> LinkedList의 맨 끝에 객체(o)를 추가. 성공하면 true
• Object peekFirst()
  ->LinkedList의 첫 번째 요소 반환
• Object peekLast()
  ->LinkedList의 마지막 요소 반환
• Object pollFirst()
  -> LinkedList의 첫 번째 요소를 반환하면서 제거
• Object pollLast()
  -> LinkedList의 마지막 요소를 반환하면서 제거
• Object pop()
  -> removeFirst()와 동일
• void push(Object o)
  -> addFirst()와 동일
• Object removeFirst()
  -> LinkedList의 첫 번째 요소 제거
• Object removeLast()
  -> LinkedList의 마지막 요소 제거
• boolean removeFirstOccurrence(Object o)
  -> LinkedList에서 첫번째로 일치하는 객체를 제거
• boolean removeLastOccurrence(Object o)
  -> LinkedList에서 마지막으로 일치하는 객체를 제거

---

ArrayList와 LinkedList

• 순차적으로 추가/삭제하는 경우 ---> ArrayList

• 중간 데이터를 추가/삭제하는 경우 ---> LinkedList

ArrayList와 LinkedList는 상황에 맞게 선택하여 사용하면 된다~

둘의 혼용하는 방법도 있는데,
작업하기 전에 데이터를 작성할 때는 ArrayList를 사용하고
작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있다.

ArrayList al = new ArrayList(1000000);
for(int i=0; i<100000; i++){
	al.add(i+"");
}
LinkedList ll = new LinkedList(al);
for(int i=0; i<1000; i++){
	ll.add(500, "x");
}

컬렉션 프레임웍에 있는 대부분의 컬렉션 클래스들은 이처럼 변환이 가능한 생성자를 제공해서 이걸 이용해서 데이터를 옮기면 된다.