[자료구조] 연결리스트 (LinkedList)

 

 

연결리스트 (LinkedList)

 

 

 

 연결리스트는 각 데이터(노드)가 다음 데이터(노드)와 연결돼 있는 자료구조입니다.

 

연결리스트는 언뜻보기에 배열과 비슷해보이지만 확연한 차이가 있습니다.

 

배열은 각 데이터가 메모리의 연속한 위치에 저장이되고, 연결리스트는 각 노드가 임의의 위치에 저장이 되며,

각 노드마다 다음 노드의 위치를 담고 있습니다.

 

 

연결리스트

 

 

 굳이 배열이 있는데 왜 연결리스트를 사용하나요? 

 

 

 

연결리스트는 배열에 비해 삽입과 삭제가 용이합니다.

 

연결리스트는 데이터 중간에 삽입이나 삭제를 할때, 연결되어있는 각 노드들만 수정해주면 됩니다.

 

반면에, 배열의 경우 삽입이나 삭제된 데이터를 기준으로 전체 배열의 인덱스를 새로 정렬해줘야하기 때문에

기술적인 비용이 더 소모됩니다.

 

데이터가 몇개 되지않을 땐, 배열을 사용해도 차이가 미비하지만,

 

전체 데이터의 갯수가 많이질 수록 배열보단 연결리스트를 통해 자료구조 하는 것이 좋습니다.

 

하지만 연결리스트의 경우, 특정인덱스로 접근하려면 처음 인덱스부터 연결을 따라 접근해야하기 때문에

데이터에 접근하는데 어려움과 불편함이 있습니다.

 

정리해보면 다음과 같습니다.

 

 

 

정리

경우	배열 (Array)	연결리스트 (LinkedList)
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.