array 배열
sort 정렬하다
linear 선형의
element 원소
index 색인
sequential 순차적인
학교에서 자료구조 관련된 수업을 들었을 때 처음 배웠던 개념이 Linked list인게 기억나네요.
그 당시 기억을 회상해보면 잘만 쓰던 Array(배열)이 있는데, 왜 굳이 Linked List를 써서 머리 아프게 또 pointer를 써야하는지 짜증났던 기억이 납니다. 심지어 둘 다 똑같은 Linear data structure인데!
왜 Linked List를 저희가 배우고 써야 되는걸까요?
- Array의 size에는 한계가 있습니다.
Array를 declare 할 때 마다, upper limit size를 정해줘야 하는 부분이 있습니다. 그 말은 즉 무한정으로 배열의 수를 증가시키기가 어려운거죠. 바꾸고 싶으면 Resize를 따로 또 해줘야합니다. 그에 반해Linked list의 경우에는 뒷 부분에 element를 붙임으로서 무한정으로 resize가 가능한거죠.
- Insert와 Delete가 굉장히 쉽습니다.
예를들어 Sorted array에 새로운 element를 넣는다고 가정해봅시다.
위 array에 3을 넣는다고 했을때, Sorted가 된 상태를 유지하면서 동시에 새로운 element를 추가하게 되면 보통 Sorting 알고리즘을 통해서 또 정렬을 해줘야합니다. 하지만 Linked list의 경우에는 Insert와 delete가 굉장히 용이합니다! Insert와 delete 관련해서는 다음 포스트에 설명 드리겠습니다.
위 두 가지만 봐도 Linked list는 충분히 매력적인 자료구조입니다. 하지만 때에 따라서 Linked list 보다 array가 조금 더 유용하게 쓰일 수 있습니다.
언제 Array가 Linked list에 보다 유용할까요?
- Linked list는 항상 순차적으로 element에 접근해야합니다.
Array의 경우는 index를 통해서 원하는 element에 손쉽게 접근이 가능합니다. 하지만 Linked list는 Index가 없고 다른 node를 pointer로 가르키고 있기 때문에 항상 순차적으로 element에 접근해야하죠. 이러한 순차적 접근 방법은 Running time에 있어서 큰 차이를 보여줍니다.
- Linked list가 Memory를 더 크게 잡아먹습니다.
Machine Architecture 수업을 들으신 분들은 알겠지만 포인터의 경우에는 항상 8 byte의 공간을 차지합니다. Linked list에 속해있는 node들은 자기들이 가지고 있는 value와 다른 node를 항상 point 해야하기 때문에 8 byte + α의 공간을 차지하게 되죠. 하지만 Array의 경우에는 data type만 가지고 있으면 되니, memory size가 linked list에 비해서 훨씬 더 절약이 됩니다.
이와 같이 Linked list의 장점 그리고 단점을 알아보았는데요. 항상 상황에 맞게 Array 또는 Linked list를 구별해서 쓰면 될 것 같습니다.