[자료구조/개념] 배열과 리스트

자료구조를 공부하다가, 아는 내용인데 자꾸 정리가 안되어서

생활코딩 및 여러 블로그를 참조하여 공부한 것을 정리해보았습니다.

배열과 리스트의 개념

배열 : 일렬로 늘어선 같은 종류의 자료 여러개를 저장하기 위한 가장 기초적인 자료구조

리스트 : 배열의 단점을 보완하여, 빈틈없는 데이터 적재의 장점을 취한 자료구조

배열과 리스트의 특징

배열 

- 인덱스가 있어, 이를 이용해 데이터를 빠르게 조회할 수 있다.

- 메모리 낭비를 초래함. 어떤 엘리먼트가 삭제되면 그 공간을 빈 공간으로 두어야 함.

- 따라서 배열 내에 데이터의 여부도 함께 체크해야할 필요가 있음.

리스트

- 리스트에서는 인덱스가 중요하지 않음. 핵심은 바로 엘리먼트들간의 순서임.

- 즉 순서가 있는 데이터의 모임이 리스트라고 할 수 있음.

- 또한 빈 엘리먼트는 허용하지 않기 땜시 메모리 재사용이 가능함. 

자바에서의 배열과 리스트

자바에서는 배열과 리스트 모두 지원함.

하지만 자바스크립트나 파이썬 처럼 기능을 제공하고 있지 않기 땜시

자바에서 배열의 원소를 추가 및 삭제하려면 직접 구현을 해야함.

하지만 자바에서는 List라는 이름의 데이터스트럭쳐를 제공하고 있음.

ArrayList, LinkedList임.

ArrayList는 동적배열이고, LinkedList는 연결리스트임.

이 두 자료구조는 배열과 비슷하지만, 배열에서 비효율적이거나 할 수 없는 작업들을

효율적으로 할 수 있도록 도와줌.

ArrayList와 LinkedList는 사용법은 거의 같지만 내부 구현이 다름.

결론적으로는 인덱스를 이용하여 데이터를 가져오는 것이 빈번하다면 ArrayList가 빠르고

데이터의 추가/삭제가 빈번하다면 LinkedList가 빠름.

※ 저장할 데이터의 개수가 정해져 있고 리스트의 중간에 데이터의 삽입, 삭제작업이 많지 않으며,

인덱스를 이용한 빠른 조회가 필요한 경우는 ArrayList를 사용하는 것이 효율적

※ 저장할 데이터의 개수가 정해져 있지 않고 리스트의 중간에 데이터의 삽입, 삭제작업이 많으며,

특정 위치의 데이터를 검색하는 작업이 많지 않은 경우에는 LinkedList를 사용하는 것이 효율적