[자바의 정석 2권] LinkedList

1) LinkedList란?

- 배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기가 쉽고 

  데이터를 읽어오는데 걸리는 시간(접근 시간, access time)이 가장 빠르다는 장점을 가지고 있지만,

  다음과 같은 단점도 가지고 있다. 

 

1. 크기를 변경할 수 없다
- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야 한다
- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다
- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
  배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 
  복사해서 이동해야 한다. 

 

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

  배열은 모든 데이터가 연속적으로 존재하지만, 링크드 리스트는 불연속적으로 존재하는 데이터를

  서로 연결(link)한 형태로 구성되어 있다. 

 

- 링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

class Node {
  Node next;   // 다음 요소의 주소를 저장
  Object obj;  // 데이터를 저장
}

 

- 링크드 리스트에서의 데이터 삭제는 간단하다.

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

 단, 하나의 참조만 변경하면 삭제가 이루어지는 것이다.

 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다. 

 

- 새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 

  추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고,

  새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다. 

 

- 링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만

  이전요소에 대한 접근은 어렵다.

  이 점을 보완한 것이 더블 링크드 리스트이다.

 

- 더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가하여

  다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐,

  그 외에는 링크드 리스트와 같다. 

 

- 더블 링크드 리스트는 링크드 리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에,

  링크드 리스트보다 더 많이 사용된다. 

class Node { 
   Node next; //다음 요소의 주소를 저장
   Node previous; // 이전 요소의 주소를 저장
   Object obj; // 데이터를 저장
}