Array, ArrayList, LinkedList 뭐가 다른지 알고 계신가요?
Array? ArrayList? LinkedList? 다 비슷한 말 인 것 같은데 어떤 점이 다른걸까요?
| Array | index로 빠르게 값을 찾을 수 있다 |
| Array List | 데이터를 빠르게 찾을 순 있지만, 삽입 & 삭제가 느리다 |
| Linked List | 데이터의 삽입 & 삭제가 빠르다 |
좀 더 자세히 알아볼까요?
Array(배열)
배열은 선언 시에 크기와 데이터 타입을 지정해주어야 합니다.
이처럼, Array(배열)은 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조입니다.
이러한 특성 때문에 데이터의 갯수가 지속적으로 늘어날 때, 혹은 최대 사이즈를 알 수 없을 때에는 사용하기에 부적합합니다.
뿐만 아니라, 만약 사용자가 특정 인덱스에 새로운 값을 넣어야 한다면 어떻게 될까요?
원래 있던 값을 뒤로 밀어내고 해당 인덱스에 값을 넣어야하는데 사이즈가 한정되어 있기에 문제가 발생하게 됩니다.
하지만 오히려 이러한 index를 이용한다면 값의 검색, 값의 위치 파악에는 용이하다는 장점이 있습니다😊
ArrayList
Array에서의 단점(사이즈가 미리 정해져 있다는 것)을 해결하기 위해 List를 사용합니다.
List에서는 배열에서처럼 크기를 정해주지 않아도 됩니다! 하지만 List에서는 순서가 중요합니다.
크기가 정해져있지 않기 때문에, 중간에 데이터의 삽입 & 삭제가 일어나더라도 문제가 없으며 index또한 가지고 있기 때문에
검색 또한 빠릅니다.
하지만 List 역시 Array에서 삽입 & 삭제의 문제점은 해결했으나 번거로움은 해결하지 못했습니다.
배열 속 값들을 일일히 당기거나 밀어주어야 하기 때문에 연산 횟수도 많아질 수 있고 메모리 낭비도 발생한다는 단점이 여전히 존재합니다.
Linked List
연결 리스트(Linked List)는 다중/단일로 나뉘는데, 종류가 무엇이든 '한 노드에 연결 될 노드의 포인터 위치를 가리키는 방식'으로 이해하면 됩니다.
단일 연결 리스트는 일방향으로 자신의 뒤에 있는 노드만 가리키고, 다중은 앞&뒤 노드를 모두 가리킨다는 점에서 차이가 있습니다.
이러한 원리를 가지고 있기 때문에 연결 리스트에서의 삽입 & 삭제는 이전까지의 번거로움을 해결했다고 볼 수 있습니다.
만약 B 다음에 B+를 삽입하고 싶다면 B에서 C로 연결된 화살표를 B+를 향하게 한 뒤 B+의 화살표를 C에 이어주면 됩니다.
삭제도 같은 원리로 동작하게 되죠.
하지만 연결 리스트는 index값을 가지고 있지 않기 때문에 순차 검색만이 가능하므로 'List의 K번째 값을 찾아라' 와 같은 문제에서는 비효율적이라는 단점이 있습니다.
이상으로 Array, ArrayList, LinkedList에 대해서 알아보았습니다!
본 글은 Gyoogle님의 Tech interview를 보고 공부한 내용임을 알려드립니다.