java LinkedList

링크드 리스트

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽다. 인덱스로 접근하기 때문에 접근시간이 빠르다는 장점을 가지고 있지만 다음과 같은 단점도 있다.

1. 크기를 변경할 수 없다.
   크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사
   충분히 큰 크기의 배열을 생성할 경우 메모리 낭비

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
   차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만 배열의 중간에 삽입하기 위해선 뒤의 데이터를 복사 후 이동해야한다.

이러한 배열의 단점을 보완하기 위해 링크드 리스트라는 자료구조가 고안되었다.

class Node{
    Node next;
    Object obj;
}
class Node{
    Node next;
    Node previous;
    Object obj;
}

메서드

void clear()	목록에서 모든 요소를 삭제합니다.
boolean add(E e)	LinkedList에 지정된 요소 추가
void add(int index,E e)	LinkedList의 지정된 인덱스에 지정된 요소를 추가합니다.
E get (int index)	지정된 인덱스의 요소를 가져옵니다.
Int indexOf (Object o)	목록에서 주어진 요소가 처음 나타나는 인덱스를 반환합니다. 요소를 찾을 수없는 경우 -1.
Int lastIndexOf (Object o)	LinkedList에서 주어진 요소의 마지막 인덱스를 반환합니다. 주어진 요소가없는 경우 -1
ListIterator listIterator (int 인덱스)	연결된 목록의 지정된 인덱스에서 listIterator를 반환합니다.
E pollFirst ()	목록의 첫 번째 요소를 반환하고 삭제합니다. 목록이 비어 있으면 null을 반환합니다.
E pollLast ()	목록의 마지막 요소를 반환하고 삭제합니다. 목록이 비어 있으면 null을 반환합니다.
E pop()	LinkedList의 첫번째 요소 제거
E set(int index, E e)	주어진 인덱스에 주어진 요소를 설정합니다. 현재 요소를 새 요소로 바꿉니다.
Int size()	LinkedList의 요소 수 또는 크기를 반환합니다.

ArrayList VS LinkedList

1. 순차적으로 추가/삭제하는 경우 → ArrayList
   순차적으로 삭제할 경우에는 중간에 요소를 삭제하고 복사하는 재배치 연산을 할 필요가 없기 때문에

2. 중간 데이터를 추가/삭제하는 경우 → LinkedList
   중간 데이터를 추가/삭제하는 경우에는 연결리스트에서 각 요소의 참조를 변경만 해주면 되기 때문에 속도가 굉장히 빠르다.

3. 배열의 n번째 요소 읽기 → ArrayList
   배열에서 인덱스 n의 주소 = 배열의 주소 + n * 데이터 타입의 크기
   ArrayList는 데이터가 연속적으로 메모리에 존재하기 때문에 위의 계산으로 데이터를 쉽게 읽을 수 있다.
   하지만 불연속적으로 위치한 LinkedList 경우에는 n번째 데이터부터 차례대로 읽어야하기 때문에 Access Time이 길다.

정리

데이터 크기의 변경이 없다 → ArrayList
데이터 변경이 잦다 → LinkedList
이런 두 리스트의 장점을 조합해서 사용하면 좋은 효율을 얻을 수 있다.
예를 들어서 처음에 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용하고, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있다.