[자료구조] 배열과 리스트 알아보기

728x90

안녕하세요 코딩테스트 준비를 위해 꼭 알아야 하는 배열과 리스트에 대해서 정리해보겠습니다.

🚨 코딩테스트를 준비하실 분이라면 배열과 리스트는 무조건적으로 알아야지 진행을 할 수 없습니다.

위 자료구조를 알지 못한다면, 코딩 테스트 준비시 많이많이 힘들 수 있으므로 꼭 알고 가야 합니다.

배열이란?

메모리의 연속적인 공간에 값이 채워져 있는 형태의 자료구조이고 인덱스를 통해 값을 참조할 수 있다.

배열의 특징?

리스트는 값과 포인트를 묶은 노드라는 것을 포인터로 연결한 자료구조 입니다.

여기서 설명하는 리스트는 여러가지 List중에서 LinkedList를 의미합니다.

노드 ⇒ 컴퓨터과학에서 값, 포인터를 쌍으로 갖는 기초 단위 입니다.

Java에서 List 인터페이스 안에는 여러가지 클래스들이 구현이 되어 있습니다

위 4가지가 있습니다. 자세한거는 구글링 해보시거나, 제가 나중에 포스팅 해서 올리겠습니다!

✔ 여기서는 LinkedList를 기준으로 설명을 하고 있으니, 알고 계셔야 합니다!

위 사진은 LinkedList 예시 사진입니다

리스트 특징

인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 합니다. 즉 값에 접근하는 속도가 느리다
포인터가 노드로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
- 배열은 삽입,삭제시 앞뒤 값을 이동시켜야하는데, 위 리스트는 노드로 연결되어 있으므로, 그 노드 중간에 값을 삽입하거나,삭제하는것이 편리하다.
선언할 때 크기를 별도로 지정하지 않아도 된다. List의 크기는 정해져 있지 않아 가변적인 데이터를 다룰 때 사용
- 배열은 크기가 정해져 있지만, List는 크기가 정해져있지 않아 유용함
```
int[] Arr = new int[10]; //배열 선언방법 (크기 지정)
List<Integer> list = new ArrayList<>(); // 리스트 선언 방법 
```
포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다

이 정도로 간단한 개념정도만 알고 있다면 코딩테스트를 진행하기 훨씬

수월해질 것입니다.

실질적으로 코테를 준비할 때, 저희는 배열, List 이 두가지를 제일 많이 사용할 것이라고 생각합니다.

문제에 따라서 어떤 자료구조를 선택해야 할지 알 수 있을 때까지 우리는 공부를 꾸준히 해야 한다고 생각합니다.

저만의 기준으로는

❗ 배열을 사용할 떄는 간단하고, 데이터의 값이 불변일 때 사용, 인덱스를 사용하여 데이터의 접근이 잦을때 사용 합니다.

❗ List는 크기가 가변적이고, 데이터 삽입 삭제가 잦을때 사용.

위 두 풀이를 보면서 읽히며 좋다고 생각합니다.

이상 포스팅 마치겠습니다 감사합니다.

ref : Do it! 알고리즘 코딩테스트(Java)

728x90