Linked List vs Array List | LIM

💡 List란
순서가 있는 데이터의 집합

 

📌 List 의 종류

List의 종류로는 Array List와 Linked List 가 있는데 두 개의 차이를 한번에 설명해주는 그림이 있어서 가져와 보았다.

java의 ArrayList, LinkedList 비교 (출처: 생활코딩)

 

 

✔️ Array List

연속적인 공간에 순차적으로 데이터를 저장

🙂 장점

- indexing 가능

 

😓 단점

- 데이터 추가/삭제가 LinkedList에 비해 오래 걸린다.

- 삽입/삭제가 빈번하게 일어날 시 시간이 오래 걸릴 수 있다.

 

 

 

✔️ Linked List

비연속적인 공간에 순서대로 데이터를 저장

🙂 장점

- 데이터의 추가/삭제가 쉽다

 

😓 단점

- Array List에 비해 인덱스 조회가 오래걸린다.

- 순차탐색으로 조회해야하기 때문에 인덱스 조회가 오래걸린다는 단점이 있다.

 

🧸 메모리에 빗대어서 더 살펴보자

메모리는 건물에 비유할 수 있다. 

 

https://opentutorials.org/module/1335/8821

 

Array List

첫 번째 회사는 모든 직원이 한 곳에 모여있어야 한다는 철학을 가지고 있어서 사무실이 모여있다.
배열은 건물을 이런식으로 사용하는 것과 비슷하다. 

만약 공간이 부족하게 되면 사람을 뽑을 수 없게 되거나 더 넓은 건물로 이사가야 한다. 

하지만 방문자가 특정 사무실을 찾을 때는 매우 빠르게 찾아서 방문할 수 있다. 

 

Linked List

두 번째 회사는 한 회사가 임대한 사무실이 떨어져있고, 덕분에 직원이 늘어나도 큰 걱정은 없다.

비어있는 곳을 임대해서 들어가면 되기 때문이다. 

하지만, 방문자가 특정 사무실을 찾기 위해서는 첫번째 사무실부터 방문하면서 다음 사무실의 위치가 어딘지 물어물어서 방문해야 한다는 비효율적인 측면이 있다. 

 

연결 리스트를 사용하는 실생활 예제로는 다음과 같은 것들이 있다.

• 멜론이나 유튜브 뮤직같은 음악 스트리밍 시스템에서 다음 곡 혹은 이전곡으로 갈 수 있는 것
• ctrl + z 로 했던 것을 지우거나 ctrl + y 로 다시 나타나게 하는 것
• 이미지 뷰어에서 다음 이미지, 혹은 이전 이미지를 볼 수 있게 하는 것