List & Array

🤷🏻‍♀️ 시작하기 전에 앞서...

✏️ 우리는 일상생활 뿐만 아니라 코드를 짜면서 같은 자료형들을 그루핑(grouping)하는 작업을 많이 하고 있을 것이다. 프로그래밍적으로 그루핑할 경우에는 배열이라는 것을 흔히 많이 들으면서 사용해 왔다. 배열뿐만아니라 리스트라는 단어도 듣는데 그때마다 배열이라는 것이 있는데 리스트라는 단어를 왜 사용할까? 어떠한 차이점이 있지? 에 대한 호기심이 커졌다.

따라서 배열과 리스트에는 어떠한 차이점이 존재하는지, 각자 어떠한 것을 정의하길래 다른 것인지 한번 알아보도록 하자!

 

💁🏻‍♂️ 배열(Array)이란?

✏️ 위키백과에서 '배열이란 인덱스와 번호에 대응하는 데이터들로 이루어진 자료구조를 나타낸다.'라고 설명하고 있다. 솔직히 이것만 봐서는 어떤 것을 의미하는지 이해하기 어렵다. 

배열은 쉽게 말해서 물리 주소와 논리 주소가 같으며 크기가 고정되어 같은 자료형의 원소들이 연속적으로 구성되어 있는 자료구조이다. 크기가 고정되어 있다는 것은 인덱스 연산자를 사용할 수 있다는 것을 의미하는데 이는 곧 빠른 검색이 가능한 것을 의미한다. 

* 배열을 선언할 때 초기화를 하지 않았다면 배열의 크기만큼 기본값이 채워진다. 배열을 초기에 10의 크기로 지정하였다면 5개의 데이터만 저장하더라도 실제 배열의 크기는 10이다. 따라서 배열을 사용하면 캐쉬히트(cache hit)의 가능성이 커져 성능에 큰 도움을 줄 수 있다.

• 캐쉬히트(cache hit)란?
  • CPU가 데이터를 요청하여 캐쉬 메모리에 접근하였을 때 캐쉬 메모리가 해당 데이터를 가지고 있는 경우를 말한다.

앞서 언급하였던 크기가 고정되어 있는 배열의 특징은 검색을 빠르게 할 수 있다는 장점을 지닐 수 있지만 새로운 원소를 삽입/삭제 시 메모리 낭비를 발생시킨다는 단점이 존재한다.

• Why?
  • 크기가 고정되어 있기 때문에 중간에 원소가 삭제 되었다고 하더라도 그 빈 공간은 계속해서 남아있기 때문이다.

🥴 다뤄야 할 데이터의 개수가 예측하기 어렵고 가변적이라면 배열의 사용을 지양하도록 하자.

 

💁🏻‍♂️ 리스트(List)란?

✏️ 위키백과에서 '리스트란 같은 값이 한번 이상 존재할 수 있는 일련의 값이 모여있는 추상적인 자료형이다.' 라고 설명하고 있다. 마찬가지로 이 설명문을 보고 한번에 이해할 수 있는 사람이 있을까...?

리스트는 쉽게 말해서 배열의 단점을 극복하기 위해 탄생한 자료구조로써, 같은 자료형으로 그루핑한 하나의 체인이라고 생각해보자. 리스트는 노드라는 체인을 가지고 있는데 첫 번째 만들어진 노드의 포인터가 두 번째 노드를 가르키고 두 번째 노드의 포인터가 세 번째 노드를 가르키는 식이다.

리스트의 체인 구조

따라서 배열의 단점이였던 원소를 삭제/삽입하는 경우 많은 시간이 소요되는데에 반해서 리스트는 포인터가 가르키는 곳만 변경해주면 되기 때문에 상대적으로 시간이 덜 소요된다는 장점을 가지고 있다.

또 다른 리스트의 특징 중 하나는 빈틈없는 데이터의 적재라는 장점을 가지고 있다.

• 빈틈없는 데이터의 적재?
  • 하나의 원소를 삭제하였을 경우 삭제된 데이터 뒤의 원소가 빈틈없이 공간을 연속적으로 위치시킨다.

하지만 다음과 같은 특징으로 인하여 인덱스 연산자가 사용되지 못하기 때문에 리스트는 데이터 조회 작업이 느릴 수 있다는 단점이 있다. 또한 순차성을 보장하지 못하기 때문에 캐쉬히트가 어렵다.

 

📝 Array & List 정리

	저장 방식	크기	속도
배열 (Array)	정해진 공간이 존재하며, 모든 곳에 인덱스 연산자가 존재	크기 할당이 필요하며 크기가 고정적이다.	데이터 삽입/삭제 : 속도 느림 데이터 검색 : 속도 빠름
리스트 (List)	인덱스 연산자가 존재하지 않는다. 앞의 요소가 삭제되면 뒤의 요소가 빈공간을 차지한다.	크기 할당이 필요 없다.	데이터 삽입/삭제 : 속도 빠름 데이터 검색 : 속도 느림

• 크기 할당을 안해도 되는 리스트가 더 사용하기 좋은 것 아닌가요?!
  • 그렇다고는 할 수 없습니다! 리스트를 사용하면 사용하지 않는 메모리 할당이 더 많아지기 때문에 크기가 정해져있는 데이터를 그룹핑하고 싶다면 배열이 더 효율적인 선택일 가능성이 높습니다.
• 배열의 크기는 length로, 리스트의 크기는 size를 사용한다!

 

🫥 언어별로 리스트를 지원하는 것이 다르다!

• C언어 = 리스트 지원x
• Java = 배열과 리스트 모두 지원, ArrayList & LinkedList로 나뉨
• JavaScript = 배열에 리스트 기능 포함

 

💁🏻‍♂️ 배열 리스트 (ArrayList)

자바에서는 배열 리스트와 연결 리스트로 나뉜다는데 어떠한 것들인지 한번 알아보자!!

배열이면 배열이지 배열 리스트??

✏️ 배열 리스트는 내부적으로 배열을 사용하여 요소를 저장하는 자료구조로써, 배열의 고정된 크기의 한계점을 해결하기 위해 탄생한 자료구조이다. 쉽게 한줄로 이해하기 위해서 배열을 이용해 리스트를 구현한 것이라고 생각하면 된다.

배열 리스트의 특징은 앞서 언급하였듯이 별도의 크기를 지정해줄 필요도 없으며 크기를 관리해줄 필요도 없다. 데이터를 삽입/삭제할 경우 연산 후 가지고 있어야 할 원소의 개수에 딱 맞춰 크기를 조정하는 특징이 있다. 이는 리스트의 빈틈없는 데이터의 적재라는 장점이 동일하게 있는 모습이다.

배열 리스트의 공간 크기는 가변적이라고 했다. 하지만 배열 리스트를 사용할 때 크기를 가변적으로 느끼게 만드는 것일 뿐 배열을 사용할 때의 복잡한 과정을 숨겨놓은 것 뿐이다.

배열과의 차이점은 저장 공간의 크기가 가변적이며 리스트의 메서드를 사용할 수 있다는 점이다. 또한 배열 리스트는 인덱스 연산자를 직접 활용하지 않고 get/set 메서드를 활용한다는 점이 존재한다.

원소를 삽입/삭제할 경우 시간적인 측면에서 배열과 차이는 없다. 즉 여전히 시간 소모가 많이 된다는 것이다.

 

💁🏻‍♂️ 연결 리스트 (LinkedList)

✏️ 연결 리스트는 배열 리스트의 원소 삽입/삭제 시 존재하는 한계점을 극복하기 위해 탄생한 자료구조이다. 연결 리스트의 저장 공간 크기 또한 리스트와 마찬가지로 가변적이며 배열 리스트와 마찬가지로 get/set 메서드를 활용한다.

쉽게 말해서 리스트와 유사한 자료구조라고 생각해면 될 것 같다.