[Java] LinkedList

배열은 구조가 간단해 사용하기 쉽고 데이터를 빠르게 읽어올 수 있지만,

크기를 변경할 수 없고, 순차적이지 않은 데이터의 추가나 삭제에 시간이 많이 걸린다.

이런 단점을 보완하기 위해 Linked List라는 자료구조를 사용한다.

 

배열은 특정 주소부터 연속적으로 값을 저장한다. (저장된 객체의 타입의 사이즈만큼 간격)

Linked List는 하나의 노드에서 값과 다음 노드의 주소 값을 갖는다. 연속적으로 두지 않아도 다음 노드를 주소로 참조하여 사용할 수 있다. (단방향이지만, Double Linked List는 이전 노드의 주소도 갖는 양방향)

 

메서드

boolean add(Object o) 지정된 객체를 끝에 추가, 성공하면 true.

void add(int index, Object element) 지정한 위치에 객체를 추가

void clear() 리스트 모든 요소를 삭제

boolean contains(Object c) 지정된 객체가 리스트에 포함되어있는지 확인

Object get(int index) 지정한 위치의 객체를 반환

int indexOf(Object o) 지정한 객체의 위치를 반환

boolean isEmpty() 리스트가 비어있는지 확인. 비어있으면 true

Object remove(int index) 지정한 위치의 객체를 삭제하고 객체를 반환

boolean remove(Object o) 지정한 객체를 삭제한다. 삭제하면 true.

Object set(int index, Object element) 지정된 위치의 객체의 값을 변경한다.

int size() 리스트에 저장된 객체의 개수를 반환한다.

List subList(int from, int to) 리스트를 from 부터 to까지 잘라 List로 반환

Object[] toArray() 리스트에 저장된 객체들을 배열로 반환

 

Queue 자료구조를 위한 메서드

Object element() 리스트의 첫 번째 요소 반환

boolean offer(Object o) 객체를 리스트 끝에 추가. 성공하면 true

Object peek() 리스트의 첫번째 요소를 반환

Object poll() 리스트의 첫번째 요소 반환하면서 리스트에서 제거

Object remove() 리스트의 첫번째 요소 제거

 

Deque 자료구조를 위한 메서드 (Java reference 참조)

Deque는 Double-Ended Queue로 한 쪽 끝으로만 추가/삭제가 가능한 Queue와 다르게 양 쪽 끝에 추가/삭제가 가능하다.

 

ArrayList는 읽고, 순차적인 데이터처리에 더 빠르다. 하지만 비순차적 데이터처리에 느리고 메모리 사용에 비효율적이다. LinkedList는 읽어 오는 시간이 느려 많은 데이터 처리에 접근성이 떨어지지만, 비순차적인 데이터 처리에 빠르다.

 

스택 (Stack)은 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다.

큐 (Queue)는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로 ArrayList와 같은 배열 기반 컬렉션 클래스를 사용하면 빈 공간을 채우기 위해 배열 복사가 반복되기 때문에 비효율적이다. 그래서 LinkedList로 구현하는 것이 적합하다.

 

자바에서 스택은 Stack 클래스로 구현해 제공한다. 큐는 Queue 인터페이스만 정의되어 있으므로 이를 구현한 클래스를 통해 사용한다.