LinkedList

 

 

크기를 변경할 수 없고, 비순차적인 데이터 추가/삭제에 시간이 많이 걸리는

배열의 단점을 보완하기 위해 고안되었다

 

배열이나 ArrayList는 물리적으로 데이터가 연속하지만

LinkedList는 불연속적인 데이터를 서로 연결(link)한 형태로 구성되어 있다

 

class Node {

     Node next;

     Object obj;

}

 

이런식으로 다음 노드의 주소값을 가짐으로써 연결시킨다

 

삭제도 간단하다!

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

이전과 다르게 새로운 데이터의 추가, 삭제가 매우 빨라졌다

 

 

여기서 이전요소에 대한 접근도 가능한 Doubly Linked List도 등장한다

 

class Node {

     Node next;

     Node previous;

     Object ob;

}

 

이렇게 이전 노드의 주소값도 가지면 끝!

 

더 접근성을 높이기 위해 처음과 끝을 연결하면 이중 원형 연결리스트가 된다

 

 

ArrayList와 LinkedList의 장단점을 이해하고 적절하게 사용해야 효율적인 코드를 작성할 수 있다

- 순차적으로 추가/삭제하는 경우엔 ArrayList가 빠르다

   주소값을 가지지 않으니 요소의 값을 null로 바꿔주기만 하면 된다

- 중간에 데이터를 추가/삭제하는 경우엔 LinkedList가 빠르다

   ArrayList는 추가 공간을 확보하거나, 공간을 채워야하기 때문에 속도가 느리다