자바 collection framwork ( LinkedList )

자바 컬렉션 프레임워크의 LinkedList 클래스에 대해서 알아보는 시간을 가져보겠습니다.

 

배열(ArrayList)은 가장 기본적인 형태의 자료구조이고 데이터의 접근속도가 빠르다는 장점이 있지만 순차적 접근이므로 중간에 데이터를 삽입하거나 제거할때 시간이 많이 걸리고 크기를 변경할 수 없다는 단점을 가지고 있습니다.

그래서 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야하므로 메모리의 낭비를 가져올 수도 있습니다.

또한 배열의 중간에 데이터를 삽입할려면 빈자리를 확보하기 위해 다른 데이터를 복사해서 이동해야합니다.

 

이런한 배열의 단점을 극복하기 위해서 LinkedList라는 자료구조가 만들어졌는데, 데이터가 불연속적으로 존재하는 데이터를 서로 연결(Link)한 형태로 구현되어 있습니다.

 

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

 

class Node {

Node next; // 다음 주소 저장

Object obj; // data 저장

}

 

LinkedList에서의 데이터의 삭제는 삭제하고자 하는 요소의 이전요소가 삭제하고자하는 요소의 다음 요소를 참조하도록 변경하면 됩니다.

또한 새로운 데이터를 추가하기 위해서는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해 주고, 새로운 요소가 그 다음 요소를 참조하도록 변경해 주면 됩니다.

 

LinkedList는 단방향이기 때문에 다음요소에 대한 접근은 간단하지만 이전 요소에 대한 접근은 간단하지 않습니다. 이 점을 보완하기 위해 만들어진 것이 double linked list입니다.

 

double linked list는 단순히 linked list에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을뿐입니다.

 

class Node {

Node next;

Node previous;

Object obj;

}

 

또한, double linked list의 접근성보다 더 향상 시킨 구조가 dubly circular linked list인데, 단순히 더블 링크드리스트의 첫번째 요소와 마지막 요소를 서로 연결시킨 것입니다. 첫번째와 마지막, 마지막과 첫번째가 연결된 구조입니다.

실제로 LinkedList는 이름과 달리 doubly circular linkd list로 구현했는데, 이것은 링크드 리스트의 단점인 낮은 접근성을 보완하기 위함 입니다.

 

아래 예제를 한번 코딩하고 실행해보겠습니다.

 

소스는 찬찬히 보시면 금방 이해하실 걸로 믿겠습니다. ^^

제 글이 도움이 되셨다면 공감버튼을 눌러주세요.^^*