배열리스트와 연결리스트의 차이 (ft. 장단점 비교)

배열리스트와 연결리스트의 차이 (ft. 장단점 비교)

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 배열리스트와 연결리스트를 비교하면서 그 차이를 분석하고

 

나아가 무엇이 더 좋은지에 대한 포스팅을 준비했습니다.

 

그래서 결국 뭐가 더 좋은걸까요? 우리는 어떤 리스트를 써야 할까요?

 

같이 한 번 알아보시죠!

 

 

 

※혹시 아직 배열리스트(arraylist)와 연결리스트(Linkedlist)에 대해서 헷갈리시는 분은 이전 포스팅을 참고해주세요 :)

 

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

링크드리스트(LinkedList)의 개념과 연산 (ft. 장단점까지)

링크드리스트(LinkedList)의 개념과 연산 (ft. 장단점까지)

 

 

- 배열리스트와 연결리스트 비교

배열리스트와 연결리스트의 시간복잡도를 먼저 한 번 비교해보겠습니다.

 

- 데이터를 마지막에 추가할 때

데이터를 제일 뒤에 붙이는 추가작업이 있을 때 LinkedList(연결리스트)는 O(N)의 시간복잡도를, 

 

왜냐하면 데이터를 하나씩 찾아가기 때문에 O(N)의 시간 복잡도를 가지게 되고,

배열리스트(Arraylist)같은 경우는 Index를 통해서 데이터를 찾아가서 추가를 하기 때문에

 

제일 뒤에 있는 데이터를 찾아 가기 위해 처음부터 끝까지 다 순회할 필요가 없습니다.

그래서 Arraylist는 O(1)의 시간 복잡도를 갖습니다.

 

※참고※

대신 배열이 꽉차 있는 경우에

배열의 사이즈를 재할당해서 데이터를 옮기는 과정이 있기 때문에

이런 경우에 O(N)까지 시간 복잡도가 늘어날 수 있다는 것은 참고로 알아두세요.
LinkedList같은 경우엔 데이터를 맨 앞에 넣는 경우,

즉 노드를 Head에 삽입하는 경우엔 무조건 O(1)의 시간복잡도를 갖습니다.

 

 

- 데이터를 중간에 추가할 때

그 다음에 데이터를 중간 중간에 삽입하는 경우입니다.

LinkedList는 무조건 그 데이터를 찾아가기 위해서 O(N)의 시간복잡도를 갖게되구요

ArrayList는 찾아가는 것은 random access를 통해서 한 번에 할 수 있지만 

 

추가한 데이터를 기준으로 뒤에 있는 데이터들은 다 한칸씩 뒤로 밀어주는 작업을 해야 하기 때문에 

O(N)의 시간복잡도를 갖게 됩니다.

 

 

- 데이터를 삭제 할 때

그 다음에 삭제하는 경우는

 

연결리스트는 배열리스트와는 다르게 데이터를 다 당겨올 필요는 없습니다. 

그냥 그 위치에 있는 포인터만 변경해주면 됩니다. 

 

그렇기 때문에 삭제 연산 자체는 O(1)의 시간 복잡도를 갖게 됩니다.

 

Array같은 경우는 삭제한 데이터 뒤에 있는 데이터들을 다시 한칸씩 당겨오는 과정에서 

 

O(N)의 시간복잡도를 갖게 됩니다.

그 다음에 검색의 경우 LinkedList는 한번씩 다 순회를 해야 하기 때문에 O(N)의 시간복잡도를 갖고,

ArrayList의 경우 random access를 통해서 O(1)의 시간 복잡도를 갖는다.

이렇게 정리할 수 있겠습니다.

 

 

배열리스트 vs 연결리스트

 

-그래서 무엇이 더 좋은걸까?

무엇이 더 좋다기 보다는 각 리스트의 장점과 단점을 알고 각 상황에 맞게 사용해야 합니다.

 

자료구조를 써야 할 때 

 

내가 이 데이터를 주로 읽는 용도로만 쓸것 같아 하는 경우가 있을 수 있고,

또는 추가나 삭제 등 변경이 자주 있을 것 같은 경우가 있을 수 있겠죠.

그럴때 데이터 자료구조의 장단점을 잘 알고 있으면 

 

각 상황에 필요한 자료구조를 잘 선택해서 사용할 수 있겠죠,

이렇게 해서 연결리스트(LinkedList)와 배열리스트(ArrayList)를 연산별로 시간복잡도를 비교를 해봤습니다.

 

로스윗의 코딩캠프는

 

미래의 개발자 여러분을 응원합니다.

 

모두 화이팅!!

 

개발자가 자료구조와 알고리즘을 알아야 하는 진짜 이유

개발자가 자료구조와 알고리즘을 알아야 하는 진짜 이유

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이