연결리스트 LinkedList

배열은 데이터 접근시간이 가장 빠르다는 장점이 있지만 크키를 변경할 수 없고 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸립니다. 이러한 배열의 단점을 보완하는 자료구조가 연결 리스트(Linked List)입니다.

 

 

 



위 그림을 보면, 연결 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 주솟값과 데이터로 구성되어 있습니다.

 

연결 리스트의 데이터 추가와 삭제 속도는 배열에 비해 빠릅니다.

새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠릅니다.

 

데이터를 삭제할 때는 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 됩니다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 빠릅니다.

 

컬렉션	읽기, 탐색 (접근시간)	삽입 / 삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름. 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐