[CS] Array VS Linked list

 * 자료구조에서 Array와 Linked list를 기술면접을 준비하고 비교해봅니다.

 

 기술면접을 볼때 왜? Array와 Linked list를 비교해서 물어보는것일까? 한번 내용을 살펴보면서 그 답을 찾아보려고 합니다.

 먼저, Array와 Linked List에 대해 확인해 봅니다.

 

* Array (배열)

• 같은 타입의 여러 변수를 하나의 묶음으로 나타낸 것으로 많은 값을 나타낼때 유용
• 연속된 메모리의 공간에 순차적으로 저장
• 배열의 크기는 고정되며, 선언 시 배열의 크기를 정하고 변경할 수 없다.

* Linked list (리스트)

•  데이터를 순처적으로 저장하는 선형 자료구조
• 불연속적 메모리 공간에 저장 (빈틈 없이 저장)
• 노드 간에 연결(link)을 통해 리스트로 구현된 객체.
  - 첫번째 노드를 헤드(Head, 머리), 마지막 노드를 테일(Tail, 꼬리)이라고 함
  - 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어짐
• 크기가 고정되어 있지 않고, 새로운 요소를 크기가 정해져 있지 않으므로 새로운 요소를 추가할 때 크기 제한에서 자유로움
• 인텍스 접근이 불가능

 

위와 같이 Array와 Linked List를 알게되었습니다. 내용을 확인했을때 장/단점이 순간순간 보였던것 같은데, 장/단점을  같이 확인해보겠습니다.

	장점	단점
Array	• 인덱스를 가지고 있어 바로 접근 가능 • 연속된 메모리 공간에 존재하여 관리 편함	• 삽입과 삭제 어렵고 오래 걸림 • 배열의 크기를 바꿀 수 없음 • 미리 공간 할당하여 공간 낭비 발생 • 연속적인 메모리 할당 필요
Linked List	• 삽입과 삭제 용이 • 크기 정해져 있지 않아 동적 생성 가능 • 사용한 메모리 재사용 가능	• 원소를 탐색할 때 임의 접근 불가능 (검색 성능 좋지 않음) • 포인터로 인한 저장 공간의 낭비 발생

 

이제 장/단점을 확인해봤습니다. 

그럼, 언제 사용되어야 하는지도 확인해보겠습니다.

	Array	Linked List
사용할 상황	• 데이터 개수가 확실하게 정해져 있을 때 • 데이터의 삭제와 삽입이 적을 때 • 검색을 해야할 때	• 크기가 정해져 있지 않을 때 • 삽입과 삭제가 자주 일어날 때 • 검색을 자주 하지 않을 때

사용할 때는, 
 * 데이터의 삽입과 삭제가 자주 일어난다면 Linked List를 사용하면 좋고,
 * 데이터의 접근하는게 부분에 비중이 높다면 Array를 사용하는것이 좋다.

 

그러면, 사용하는데 있어 데이터 처리 관련해서 사용 여부를 이야기하고 있습니다. 어떻게 처리되길래 위와 같이 이야기 할 수 있는지 살펴 보겠습니다.

(데이터)	Array	Linked List
접근 속도	• 인덱스를 사용하여 빠르게 원소에 접근 • Random Access 지원 • 시간 복잡도 O(1)로 빠르게 찾음	• 순차 접근 방식 사용 • 특정 원소 접근 위해선 처음부터 끝까지 순차적으로 검색하면서 찾음 • 시간복잡도 O(N)
삽입 속도	• 중간 or 맨 앞에 삽입 시 데이터를 한 칸씩 미뤄야 하는 추가과정 발생 • 모든 공간이 다 차버리면, 새로운 메모리 공간 할당 필요	• 어느 곳에 삽입하던지 O(N) 가짐 • 추가하고자 하는 원소 앞 Or 노드로 가서 가리키고 있는 주소만 추가해주면 되기에 빠른 삽입 가능
삭제 속도	• 그 위치의 데이터를 삭제 후, 전체적으로 Shift 해줘야 함. O(N)	• O(N)의 시간 복잡도를 갖고 삭제

이런 이유로 위와 같이 Array는 데이터의 접근(검색)할때, Linked List는 데이터 삽입/삭제가 자주 발생될 때 사용하게 되는것입니다.

 

이렇게 되는 부분은 메모리의 할당되는 부분에서의 차이가 있어서 위와 같이 2개 자료구조의 차이점이 발생되는것 같습니다.

 

• Array는 메모리에 선언되자 마자 Complie time에 할당되는데 이를 정적 메모리 할당이라고 합니다. 

      즉, Stack 영역에 메모리 할당이 이루어진다는것을 이야기 합니다.

 

• Linked list는 메모리에 새로운 node가 추가될 때 runtime에 할당되는 이를 동적 메모리 할당이라고 합니다.

       즉, Heap 영역에 메모리 할당이 이루어진다는것을 이야기 합니다.

 

이렇게 Array와 Linked list를 알아보게 되었습니다.

2개를 놓고 보니 극명하게 차이도 나는것을 알게 되고, 언제 사용되어야 효율적인지 알게 되었습니다. 

 

이로써, 면접에서 물어보는 이유를 생각해봤을 땐 자료구조에 대해 공부를 해봤는지, 연속적인 데이터 처리(삽입/삭제/검색)에 대해 고민을 해봤는지 물어보는게 아닐까 싶습니다.....

 

제 의견은 그렇습니다~

 

조금 더 정확한 이유를 알게되면 추가적으로 내용을 수정하겠습니다.

 

그런데, 실제 로직을 구현을 할때는 linked list를 많이 사용하지 않았던것 같다.. 그 이유는 연속된 데이터를 삽입/삭제만 하는게 아니라, 검색을 하는경우도 많이 있기 때문에 linked list보다는 Arraylist 또는 Array를 사용하게 되는 것 같습니다.

 

그렇기 때문에 물어보는 정확한 이유에 대해 체감되지 않아 추측성으로 답을 적었습니다.

 

긴글을 읽어주셔서 감사합니다.

 

* 참고자료

https://velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4Array%EA%B3%BC-%EB%A6%AC%EC%8A%A4%ED%8A%B8List

[자료구조] 배열(Array)과 리스트(List)

https://opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)

https://velog.io/@adam2/Array%EC%99%80-List%EA%B7%B8%EB%A6%AC%EA%B3%A0-Java-List

[자료구조]Array와 List(그리고 Java List)

https://devlog-wjdrbs96.tistory.com/64

[JAVA]ArrayList와 LinkedList의 차이

https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/

[Data Structure] Array vs LinkedList