[Data Structure] Array와 LinkedList의 차이

jjong_gang·2022년 3월 31일

시작

코딩을 하다보면 마주치게 되는 대표적인 자료구조인 Array와 Linked List의 차이가 무엇인지, 언제 어떤 것을 사용하면 좋을지에 대해서 알아보겠습니다!

Array List

배열은 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다

Array List는 아래와 같은 형태입니다.

각 요소마다 인덱스가 붙어있어, random access가 가능하고,
모든 요소가 붙어있는 형태로 존재하여, 메모리의 상대주소 계산이 가능합니다.
Array List의 시작 주소를 알고 있고, Array List 에 있는 요소들의 변수 type이 동일하기 때문에, 변수 type의 크기와 인덱스 숫자로 찾아갈 인덱스의 메모리 주소를 즉각적으로 계산할 수 있습니다.

Array List의 random access(O(1))가 가능한 특징은 다른 자료구조에 비해, 조회 속도 면에서의 이점을 가지게 됩니다.

하지만, Array List의 삽입 과정은 상대적으로 느립니다.
요소를 삽입할 위치까지 이동해야하고 (O(1)), 요소를 삽입한 뒤에는 array의 요소들을 shift(O(N))해야하기 때문입니다.

Linked List

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다

Linked List는 아래와 같은 모양을 하고 있습니다.

Array List와 다르게 각 요소들이 붙어있지 않으므로, 그에 따라 random access가 불가능합니다.
예를들어, 다섯 번째 요소인 12를 찾아가기 위해서 Array List에서는 단순하게 다섯 번째 인덱스의 메모리 주소를 계산하여 random access를 하면 됐지만, Linked List에서는 1의 다음 노드인 7을 찾아가고 그 7에 저장돼있는 다음 노드의 정보를 따라 3으로 가고 4를 거쳐 12에 도달하게 됩니다(O(N)).

그러므로, Array List에 비해 Linked List의 조회 속도는 느리다고 할 수 있습니다.

하지만, Linked List의 장점은 요소의 삽입/삭제에 있습니다. Array List에서는 새로운 요소가 들어올 때 들어온 요소의 뒤로 있는 요소들을 모두 shift 해주거나, 삭제할 때도 똑같이 빈자리를 채워주기 위해 뒤의 요소들을 shift해줘야 합니다. 이와 다르게 Linked List는 노드의 앞, 뒤의 element의 next값(다음으로 찾아가야 하는 노드의 메모리값)만 변경해주면 되므로, 요소의 삽입/삭제(O(1))가 빠르다는 장점이 있습니다.