[자바(JAVA)] 배열과 LinkedList의 장단점,이중 연결 리스트, ArrayList vs LinkedList 성능 비교

🔷배열의 장단점

👉장점: 데이터를 읽는데 걸리는 시간(접근시간, access time)이 짧다.

- n번째의 주소를 알아낼 수 있다.

 

 

👉 단점1: 크기를 변경할 수 없다.

- 크기를 변경해야 하는 경우 ① 더 큰 배열을 생성한 후 ② 데이터를 복사해야한다.

- 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면 메모리가 낭비된다.

 

👉 단점2: 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

- 데이터를 추가하거나 삭제하기 위해 다른 데이터를 옮겨야 함

- 그러나 순차적인 데이처 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

 

*비순차적인 데이터: 배열의 중간에 있는 데이터

 

---

🌟배열의 단점을 보완한게 LinkedList이다.

 1. 크기변경 불가

 2. 추가,삭제시 시간소요 큼

 

🔷LinkedList

배열과는 달리 불연속적으로 존재하는 데이터를 연결(link)한것

 

- 불연속적이다

- 마치 기차를 연결한것과 같다. = 변경에 유리함

 

 

 

<삭제시>

 

삭제시 노드(참조값)만 바꾸면 된다.

수정시에는 두번의 참조변경만 진행하면 된다.

 

 

 

---

🔷LinkedList 이중 연결리스트

 

LinkedList는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.

이 점을 보안한게 이중 연결리스트이다.

 

불연속적이라 접근성이 나쁜것을 보완하기위해 나온것으로

앞 뒤로 이동할 수 있게 연결한것이다.

 

처음 인덱스와 마지막인덱스를 연결한 doubly circuial linked list도 있다.

 

 

 

 

---

 

🔷ArrayList vs LinkedList 성능 비교

단위는 ms

1) 순차적으로 추가/삭제할 때 LinkedList는 각 객체를 하나씩 만들고 찾아야해서 이때는 ArrayList가 더 빠르다.

2) 비순차적으로 데이터를 추가/삭제 - LinkedList가 더 빠르다.

3) 접근시간 - ArrayList가 더 빠르다.

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

 

 

 

<결론>

 

ArrayList : 배열 기반(연속적)

LinkedList: 연결 기반(불연속적)

 

 

다루고자 하는 데이터의 개수가 변하지 않는 경우라면 ArrayList를 추천
데이터 개수의 변경이 잦다면 LinkedList를 사용하길 추천함

*처음 작업전에 데이터를 저장할 때는 ArrayList를 사용한 다음, 작업시에는 LinkedList로 데이터를 옮겨서 작업하면 더 좋은 효율을 낼 수 있다. 

 

 

 

 

이 외에도 여러가지 컬렉션이 있고, 데이터를 잘 다루기 위해서는 어떤식으로 저장되는지, 어떤 구조로 정해야 하는지를 파악해야한다.