어레이와 리스트의 차이

서론

어레이에는 정적어레이, 동적어레이가 있다.

어레이와 리스트의 차이점은 무엇이고 각각은 어떤 상황에서 가장 쓰기 적합할까?

본론

어레이와 리스트의 가장 큰 차이점은 "연결되어 있냐" 일 것이다.

어레이는 말 그대로 데이터들이 연속적인 메모리에 저장되어있는것이다.

이때 정적어레이는 선언 시에 그 크기가 정해지고 런타임에서는 크기를 변경할 수 없다.

즉, int arr [10];이라고 선언한 후에 이 크기를 다른 크기로 변경할 수 없다는 말이다. 하지만 이와는 별개로 배열은 연속적으로 저장되어 있다. 즉 arr의 데이터들의 메모리 위치를 보면 arr [0]과 arr [1]의 차이는 int의 크기만큼인 4byte이다. 즉 연속되어 저장된다는 말이다. 

동적어레이는 런타임에 크기 변경이 가능하고 메모리의 위치를 보면 정적어레이와 동일하게 연속된 메모리에 위치한다.

이때 주의 할 점은 동적어레이의 크기를 변경할 때 그 동적어레이의 첫 번째 인자가 가리키는 주솟값은 변경된다는 것이다. 즉 원래있던 공간의 뒷쪽에 추가적인 공간을 붙이는 방식이아니라. 완전히 새로운 공간을 만들어서 이전의 벡터를 복사한 후 기존의 벡터는 삭제하는 형식으로 진행되기 때문에 첫번째 인자가 가리키는 주솟값은 변경된다.

또한 어레이는 인덱스로 접근이 가능하다. 따라서 원소에 접근할 때는 O(1)의 복잡도로 실행할 수 있다.

하지만, 연속적인 선형구조로 되어있기 때문에 배열의 중간에 새로운 값을 넣거나 또는 삭제하는 것은 O(n)의 시간복잡도가 소요된다.

어레이는 연속적인 메모리에 위치해 있기 때문에 캐시 관점에서 보았을 때 공간 지역성(Spacial Locality)이 좋아서 높은 캐시 hit rate를 가진다고 볼 수 있다.

 

 

이와 다르게 리스트는 각각의 데이터가 저장되는 node들이 연속적이지 않고 무작위로 떨어져 있다. 대신에 하나의 node에 다음 node를 가리키는 pointer에 대한 정보가 저장되어 있어서 다음 데이터에 접근을 할 수 있다.

연속적으로 배치되어 있는 것이 아니기 때문에 index로 접근이 불가하고 어떠한 원소에 접근하기 위해서는 O(n)의 복잡도가 소요된다. 하지만 각각의 node들은 pointer로 연결되어 있기 때문에 중간의 값을 삽입하거나 삭제할 때는 이 포인터만 조정하면 되기 때문에 O(1)의 시간복잡도가 소요된다.

하나 특정 위치를 찾아가서 삭제나 삽입을 한다고 하면 O(n+1)로 결국 O(n)의 복잡도를 가지긴 한다.

 

위의 특징들을 보았을 때

Array의 활용 상황

1. 데이터 접근이 중요한 경우:
   • index로 접근 가능 O(1)
2. 데이터 크기가 고정된 경우:
   • 표, 행렬 연산 
3. 캐시 최적화가 중요한 경우:
   • 데이터가 연속적이라 cache Hit Rate가 높음

 

LinkedList의 활용 상황

1. 삽입/삭제가 빈번한 경우:
   • 예: queue나 stack 구현.
   • 데이터가 동적으로 추가되거나 제거되는 환경에서 메모리 재할당 없이 유연하게 동작.
2. 데이터 크기가 가변적인 경우:
   • 예: 실시간 데이터 흐름 처리.
   • 데이터의 크기를 미리 알 수 없는 상황에서 효과적.
3. 캐시 효율이 덜 중요한 경우:
   • 예: 그래프의 인접 리스트 구현.
   • 데이터가 랜덤 하게 저장되어도 성능 저하가 큰 영향을 주지 않는 경우.

결론

 

어레이는 연속적인 메모리에 위치하고 리스트는 비연속적인 메모리에 위치한다.

각각의 특성에 맞게 알맞은 상황에 사용하자

 

마무리

어레이와 리스트의 차이점과 각각의 활용 상황을 알아보았다.

 

위의 내용을 바탕으로 개발자 면접 간

1. 어레이와 리스트의 차이점은 무엇인가요?

 

등에 대한 질문을 생각해 볼 수 있겠다. 스스로에게 질문을 해보고 답해보자.

 

헷갈리는 부분은 보완하기! 찡긋 O.<

 

틀린 부분이나 보완해줬으면 하는 내용이 있으면 댓글로 알려주세요! 추가 설명이 필요하신 부분도 댓글로 알려주세요.

어떠한 피드백도 환영입니다. 긴 글 읽어주셔서 감사합니다.