연결 리스트(Linked List)

ohwoo-kwon·2022년 3월 22일
0

DataStructure

목록 보기
2/3

연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조로 각 노드는 데이터를 가지고 있으며 다음 노드의 위치를 가리키고 있습니다. 배열에 비하여 추가/삭제 작업은 빠르지만 데이터 접근에는 많이 비용이 소모됩니다.

배열(Array)은 크기가 정해져 있지만 연결 리스트는 크기가 정해져 있지 않다는 장점이 있습니다. 또한 연결 리스트는 배열보다는 추가/삭제 작업에 드는 비용이 크지 않습니다. 이번에도 오마이걸과 함께 연결 리스트의 특징에 대해 설명해보겠습니다.

위의 그림처럼 오마이걸은 자신의 생일과 일치하는 주소에 들어있고 포인터를 이용해 다음 멤버가 들어있는 주소를 가리키고 있습니다. 여기서 연결 리스트의 가장 앞을 Head, 가장 끝을 Tail 이라고 부릅니다. 연결 리스트는 항상 Head의 값을 가지고 있습니다. 따라서 데이터를 읽어오기 위해서 Head를 시작으로 순서대로 값을 찾아야 합니다. 만약 승희를 찾기 위해서는 효정 > 미미 > 유아 > 승희 순으로 읽어오는 것이죠. 따라서 길이가 N인 연결 리스트에서는 데이터를 읽는데 최악의 경우 O(N)의 시간 복잡도를 가지게 됩니다.
추가/삭제의 경우는 배열보다는 조금 간단한게 작동합니다. 배열이 추가/삭제 작업 시에 요소들을 shift 했던 것과 달리 연결 리스트는 포인터를 변경만 해주면 됩니다. 만약 제가 오마이걸 멤버로 합류하고 싶다면 아래의 그림처럼 포인터가 가리키는 주소를 변경해주면 됩니다. 추가/삭제만 본다면 O(1)의 시간 복잡도를 가질 것 같지만 연결 리스트에서 추가/삭제를 해야하는 노드를 찾아야 하므로 결과적으로는 O(N)의 시간 복잡도를 가지게 됩니다.

profile
피드백을 즐기는 FE 개발자

0개의 댓글