[Java] Class LinkedList
JavaCollection Framework
데이터 군을 저장하는 클래스들을 표준화한 설계
컬렉션 Collection : 다수의 데이터. 데이터 그룹
프레임웍 Framework : 표준화된 프로그래밍 방식.
Class LinkedList
배열의 단점을 보완하기 위해 고안된 자료 구조.
불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성.
구성
각 요소(Node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev; // Doubly-LinkedList
}- array = 0x100
| 0x100 | 0 | 1 | 2 | 3 | 4 |
|---|
- LinkedList = 0x200
| 0x200 | 0x300 | 0x350 | 0x370 | 0x400 | |
|---|---|---|---|---|---|
| next | 0x300 | 0x350 | 0x370 | 0x400 | null |
| item | 0 | 1 | 2 | 3 | 4 |
삭제
삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경한다.
단 하나의 참조만 변경하면 되므로 처리 속도가 매우 빠르다.
| 0x200 | 0x300 | 0x370 | 0x400 | |
|---|---|---|---|---|
| next | 0x300 | 0x370 | 0x400 | null |
| item | 0 | 1 | 3 | 4 |
추가
새로운 요소를 생성한 후 추가하고자 하는 위치의 이전 요소의 참조를
새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경한다.
처리 속도가 매우 빠르다.
| 0x200 | 0x250 | 0x300 | 0x370 | 0x400 | |
|---|---|---|---|---|---|
| next | 0x250 | 0x300 | 0x370 | 0x400 | null |
| item | 0 | 5 | 1 | 3 | 4 |
접근성
이동 방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만, 이전 요소에 대한 접근이 어렵다.
- Doubly-LinkedList
이중 연결 리스트
LinkedList의 접근성을 보완한 것.
참조변수를 하나 더 추가하여 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외는 LinkedList와 동일하다.
접근과 이동이 쉽기 때문에 LinkedList보다 많이 사용된다.
- LinkedList ex) 0x200
| 0x200 | 0x300 | 0x350 | 0x370 | 0x400 | |
|---|---|---|---|---|---|
| next | 0x300 | 0x350 | 0x370 | 0x400 | null |
| item | 0 | 1 | 2 | 3 | 4 |
- Doubly-LinkedList ex) 0x200
| 0x200 | 0x300 | 0x350 | 0x370 | 0x400 | |
|---|---|---|---|---|---|
| next | 0x300 | 0x350 | 0x370 | 0x400 | null |
| prev | null | 0x200 | 0x300 | 0x350 | 0x370 |
| item | 0 | 0 | 0 | 0 | 0 |
- Doubly Circular LinkedList
이중 원형 연결 리스트
Doubly-LinkedList보다 접근성을 향상 시킨 것.
단순히 Doubly-LinkedList의 첫 번째 요소와 마지막 요소를 서로 연결시켰다.
실제로 LinkedList 클래스는 이름과 달리, 낮은 접근성(accessability)을 높이기 위해 Doubly Circular LinkedList로 구현했다.
| 0x200 | 0x300 | 0x350 | 0x370 | 0x400 | |
|---|---|---|---|---|---|
| next | 0x300 | 0x350 | 0x370 | 0x400 | 0x200 |
| prev | 0x400 | 0x200 | 0x300 | 0x350 | 0x370 |
| item | 0 | 0 | 0 | 0 | 0 |
Public constructors
| 생성자 | 설명 |
|---|---|
| LinkedList() | LinkedList 객체 생성 |
| LinkedList(Collection<? extends E> c) | 주어진 컬렉션을 포함하는 LinckedList 객체 생성 |
Public methods
List 인터페이스를 구현했기 때문에 ArrayList와 내부 구현 방법만 다를 뿐 제공하는 메서드의 종류와 기능은 거의 같다.
| 반환 타입 | 메서드 | 설명 |
|---|---|---|
| boolean | add(E e) | 지정된 객체를 LinkedList의 끝에 추가. 성공하면 true |
| void | add(int index, E element) | 지정된 위치에 객체 추가 |
| boolean | addAll(Collection<? extends E> c) | 주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가 성공하면 true |
| boolean | addAll(int index, Collection<? extends E> c) | 지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 추가 성공하면 true |
| void | addFirst(E e) | LinkedList의 맨 앞에 객체 추가 |
| void | addLast(E e) | LinkedList의 맨 끝에 객체 추가 |
| void | clear() | LinkedList의 모든 요소를 삭제 |
| boolean | contains(Object o) | 지정된 객체가 LinkedList에 포함되어있는 지 확인 |
| E | element() | LinkedList의 첫 번째 요소 반환 |
| E | get(int index) | 지정된 위치의 객체를 반환 |
| E | getFirst() | LinkedList의 첫 번째 요소 반환 |
| E | getLast() | LinkedList의 마지막 요소 반환 |
| int | indexOf(Object o) | 지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환 |
| int | lastIndexOf(Object o) | 지정된 객체의 위치(끝부터. 역순으로)를 반환 |
| ListIterator | listIterator(int index) | 지정된 위치에서부터 시작하는 ListIterator 반환 |
| boolean | offer(E e) | 지정된 객체를 LinkedList의 끝에 추가. 성공하면 true |
| boolean | offerFirst(E e) | LinkedList의 맨 앞에 객체 추가. 성공하면 true |
| boolean | offerLast(E e) | LinkedList의 맨 끝에 객체 추가. 성공하면 true |
| E | peek() | LinkedList의 첫 번째 요소를 반환 |
| E | peekFirst() | LinkedList의 첫 번째 요소를 반환 |
| E | peekLast() | LinkedList의 마지막 요소를 반환 |
| E | poll() | LinkedList의 첫 번째 요소를 반환하면서 제거 |
| E | pollFirst() | LinkedList의 첫 번째 요소를 반환하면서 제거 |
| E | pollLast() | LinkedList의 마지막 요소를 반환하면서 제거 |
| E | pop() | LinkedList의 첫 번째 요소 제거 |
| void | push(E e) | LinkedList의 맨 앞에 객체 추가 |
| E | remove(int index) | 지정된 위치의 객체를 LinkedList에서 제거 |
| E | remove() | LinkedList의 첫 번째 요소 제거 |
| boolean | remove(Object o) | 지정된 객체를 LinkedList에서 제거. 성공하면 true |
| E | removeFirst() | LinkedList의 첫 번째 요소 제거 |
| boolean | removeFirstOccurrence(Object o) | LinkedList에서 첫 번째로 일치하는 객체를 제거 |
| E | removeLast() | LinkedList의 마지막 요소 제거 |
| boolean | removeLastOccurrence(Object o) | LinkedList에서 마지막으로 일치하는 객체를 제거 |
| E | set(int index, E element) | 지정된 위치의 객체를 주어진 객체로 변경 |
| int | size() | LinkedList에 저장된 객체의 수를 반환 |
| Object[] | toArray() | LinkedList에 저장된 객체를 배열로 반환 |
| T[] | toArray(T[] a) | LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환 |
ArrayList vs.LinkedList
- 순차적으로 추가/삭제 (ArrayList의 크기가 충분한 경우)
작업 속도 : ArrayList > LinkedList
만일 ArrayList의 크기가 충분하지 않으면 LinkedList가 더 빠를 수 있다.
- 중간 데이터를 추가/삭제 (데이터가 많을 경우)
작업 속도 : ArrayList < LinkedList
데이터의 개수가 적다면 어느 것을 사용해도 큰 차이가 없다.
| 컬렉션 | 읽기(접근시간) | 추가/삭제 | 비고 |
|---|---|---|---|
| ArrayList | 빠름 | 느림 | 순차적인 추가/삭제는 더 빠름. 비효율적인 메모리 사용 |
| LinkedList | 느림 | 빠름 | 데이터가 많을 수록 접근성이 떨어짐 |
ArrayList & LinkedList
다루고자 하는 데이터의 개수가 변하지 않는 다면 ArrayList
데이터 개수의 변경이 잦다면 LinkedList
• 조합
처음에 작업하기 전에 데이터를 저장할 때 ArrayList를 사용한 후,
작업할 때 LinkedList로 데이터를 옮겨서 작업하여 효율을 높일 수 있다.
ArrayList al = new ArrayList(100000);
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");참고 서적: 자바의 정석 3판 2
