LinkedList

배열의 장단점을 알아보겠습니다. 

장점

배열은 구조가 간단하고 데이터를 읽는 데 걸리는 접근 시간이 짧습니다.

첫번째 요소를 읽는 접근시간와 마지막 요소를 읽는 접근시간이 동일합니다. 

단점

크기를 변경할 수 없습니다. 따라서 더 큰 배열을 생성 후 기존 내용을 복사한 뒤 참조 변경을 해야합니다. 

크기 변경을 피하기위해 처음부터 큰 배열을 생성하면 저장공간은 넉넉하겠지만 메모리가 낭비됩니다.

또 하나의 단점으로는 비순차적인(중간에) 데이터의 추가, 삭제 시 시간이 많이 걸립니다. (추가, 삭제 한 부분에 채워야 되기 때문에 다른 데이터를 옮겨야하기 때문입니다.) 하지만 맨 끝에 추가, 삭제하는 것은 시간이 별로 안걸립니다. (순차적 삭제는 빠름)

 

 

정리해보자면 배열은 크기 변경이 불가하고 추가, 삭제 시 시간이 많이 걸립니다. 이러한 단점을 보완하기 위해 나온 것이 LinkedList입니다. 

배열과 달리 링크드리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어있습니다. 

데이터의 삭제든 단 하나의 참조만 변경하면 됩니다. 

데이터를 추가할 때는 한번의 Node객체생성과 두 번의 참조로 변경만 하면되므로 처리속도가 빠릅니다. 

 

링크드리스트에도 단점이 있습니다. 불연속적이기때문에 접근성이 나쁩니다. 

링크드리스트를 보완한 것이 더블링크드리스트입니다. 

서로 근접한 두 요소를 앞 뒤로 이동할 수 있게 연결한 리스트입니다. 따라서 다음요소, 이전요소를 가지고 있습니다. 앞뒤로 이동할 수 있는 대신 시간이 더 걸립니다. 

이중원형연결리스트는 마지막 요소의 다음을 맨 앞으로 지정하고,  맨 처음의 요소와 맨 끝 요소를 연결한 리스트입니다. 맨 처음에서 끝으로 이동할 때 바로 맨 끝으로 이동할 수 있습니다.