안녕하세요 코딩테스트 준비를 위해 꼭 알아야 하는 배열과 리스트에 대해서 정리해보겠습니다.
🚨 코딩테스트를 준비하실 분이라면 배열과 리스트는 무조건적으로 알아야지 진행을 할 수 없습니다.
위 자료구조를 알지 못한다면, 코딩 테스트 준비시 많이많이 힘들 수 있으므로 꼭 알고 가야 합니다.
배열이란?
메모리의 연속적인 공간에 값이 채워져 있는 형태의 자료구조이고 인덱스를 통해 값을 참조할 수 있다.
배열의 특징?
- 인덱스를 통해 값에 접근한다
- 새로운 값을 삽입하거나, 특정 인덱스 값 삭제하기 어렵다.
- 삽입,삭제를 하려면 주변 값을 이동시키는 과정이 필요합니다.
- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기 변경 불가능
- 구조가 간단해서 코딩 테스트에서 제일 많이 사용합니다.
리스트란?
리스트는 값과 포인트를 묶은 노드라는 것을 포인터로 연결한 자료구조 입니다.
여기서 설명하는 리스트는 여러가지 List중에서 LinkedList를 의미합니다.
노드 ⇒ 컴퓨터과학에서 값, 포인터를 쌍으로 갖는 기초 단위 입니다.
Java에서 List 인터페이스 안에는 여러가지 클래스들이 구현이 되어 있습니다
- ArrayList
- LinkedList
- Vector
- Stack
위 4가지가 있습니다. 자세한거는 구글링 해보시거나, 제가 나중에 포스팅 해서 올리겠습니다!
✔ 여기서는 LinkedList를 기준으로 설명을 하고 있으니, 알고 계셔야 합니다!
위 사진은 LinkedList 예시 사진입니다
리스트 특징
- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 합니다. 즉 값에 접근하는 속도가 느리다
- 포인터가 노드로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
- 배열은 삽입,삭제시 앞뒤 값을 이동시켜야하는데, 위 리스트는 노드로 연결되어 있으므로, 그 노드 중간에 값을 삽입하거나,삭제하는것이 편리하다.
- 선언할 때 크기를 별도로 지정하지 않아도 된다. List의 크기는 정해져 있지 않아 가변적인 데이터를 다룰 때 사용
- 배열은 크기가 정해져 있지만, List는 크기가 정해져있지 않아 유용함
int[] Arr = new int[10]; //배열 선언방법 (크기 지정) List<Integer> list = new ArrayList<>(); // 리스트 선언 방법 - 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다
이 정도로 간단한 개념정도만 알고 있다면 코딩테스트를 진행하기 훨씬
수월해질 것입니다.
실질적으로 코테를 준비할 때, 저희는 배열, List 이 두가지를 제일 많이 사용할 것이라고 생각합니다.
문제에 따라서 어떤 자료구조를 선택해야 할지 알 수 있을 때까지 우리는 공부를 꾸준히 해야 한다고 생각합니다.
저만의 기준으로는
❗ 배열을 사용할 떄는 간단하고, 데이터의 값이 불변일 때 사용, 인덱스를 사용하여 데이터의 접근이 잦을때 사용 합니다.
❗ List는 크기가 가변적이고, 데이터 삽입 삭제가 잦을때 사용.
배열과 리스트를 사용한 예제
2023.07.27 - [코딩테스트/백준] - [Java]백준11720_숫자의 합 구하기
2023.07.28 - [코딩테스트/백준] - [Java]백준1546_평균구하기
위 두 풀이를 보면서 읽히며 좋다고 생각합니다.
이상 포스팅 마치겠습니다 감사합니다.
ref : https://www.youtube.com/watch?v=MDeAbo_LP1U&t=1s
ref : Do it! 알고리즘 코딩테스트(Java)
