Dico

[Java] Class LinkedList

Collection Framework

데이터 군을 저장하는 클래스들을 표준화한 설계

컬렉션 Collection :  다수의 데이터. 데이터 그룹

프레임웍 Framework :  표준화된 프로그래밍 방식.

Class LinkedList

배열의 단점을 보완하기 위해 고안된 자료 구조.

불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성.

구성

각 요소(Node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

private static class Node<E> {
       E item;
       Node<E> next;
       Node<E> prev;         // Doubly-LinkedList
}
  • array = 0x100
0x10001234
  • LinkedList = 0x200
0x2000x3000x3500x3700x400
next0x3000x3500x3700x400null
item01234

삭제

삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경한다.

단 하나의 참조만 변경하면 되므로 처리 속도가 매우 빠르다.

0x2000x3000x3700x400
next0x3000x3700x400null
item0134

추가

새로운 요소를 생성한 후 추가하고자 하는 위치의 이전 요소의 참조를

새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경한다.

처리 속도가 매우 빠르다.

0x2000x2500x3000x3700x400
next0x2500x3000x3700x400null
item05134

접근성

이동 방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만, 이전 요소에 대한 접근이 어렵다.

  • Doubly-LinkedList

    이중 연결 리스트

    LinkedList의 접근성을 보완한 것.

    참조변수를 하나 더 추가하여 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외는 LinkedList와 동일하다.

    접근과 이동이 쉽기 때문에 LinkedList보다 많이 사용된다.

    -  LinkedList  ex) 0x200

0x2000x3000x3500x3700x400
next0x3000x3500x3700x400null
item01234

    -  Doubly-LinkedList  ex) 0x200

0x2000x3000x3500x3700x400
next0x3000x3500x3700x400null
prevnull0x2000x3000x3500x370
item00000
  • Doubly Circular LinkedList

     이중 원형 연결 리스트

     Doubly-LinkedList보다 접근성을 향상 시킨 것.

     단순히 Doubly-LinkedList의 첫 번째 요소와 마지막 요소를 서로 연결시켰다.

     실제로 LinkedList 클래스는 이름과 달리, 낮은 접근성(accessability)을 높이기 위해 Doubly Circular LinkedList로 구현했다.

0x2000x3000x3500x3700x400
next0x3000x3500x3700x4000x200
prev0x4000x2000x3000x3500x370
item00000

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");

LinkedList API

참고 서적: 자바의 정석 3판 2