연결리스트_일반 배열 vs 연결리스트 [3/3]

일반 배열과 연결리스트는 비슷한 개념이지만, 사용 여부는 '순서'에 따라 달라질 것 같습니다.

• 일반 배열 : 들어온 순서대로 데이터가 쌓일 때 유리
• 연결리스트 : 들어온 순서가 관계 없이 특정 기준으로 데이터가 항상 정렬되어야 할 때 유리

---

 

[일반배열]

• 데이터 순서를 변경할 때 해당 순서 뒤의 데이터를 모두 복사-붙여넣기 해줘야함
• 중간에 데이터가 들어오거나 삭제될 때마다 뒷 순서의 배열을 모두 옮겨주는 작업이 발생
• 데이터 변경이 많을 수록 비효율적인 구조가 됨

 

• 배열의 크기는 미리 정해놔야하기 때문에, 빈 메모리 공간이 발생하여 비효율 초래
• 배열이 꽉 차 새로 메모리를 할당할 경우, 모든 데이터를 복사하는 작업 발생

 

※ Point
따라서 데이터의 순서변경이 잦거나, 쌓이는 데이터의 수량을 적절히 파악하기 힘들 때 일반 배열은 연결리스트에 비해 비효율적이라 할 수 있음

 

---

 

[연결 리스트]

• 데이터 순서 변경 시, 아무리 많은 데이터가 있어도 앞 노드의 포인터 변수 값만 변경해주면 됨
• 일반 배열에 비해 순서 변경에 효율적인 구조

 

• 다만 적절한 데이터 수량이 정해져 있는 경우라면, 일반 배열 대비 메모리가 더 사용됨
• 조회 시 데이터 순서를 알고 있다면 일반 배열에서는 n번째의 데이터를 바로 조회 가능하지만, 연결리스트에서는 처음(head) 또는 기준점(tail등)부터 해당 순서까지 모두 검색해야 함

 

※ Point
따라서 순서대로 저장이 되어, 순서에 따른 조회가 많이 수행되는 경우 일반 배열에 비해 비효율적이라고 볼 수 있음

 

---

 

위와 같이 각기 장단점이 존재하기 때문에 데이터 구조에 따라 적절한 저장 방식을 채택하면 되고, 필요에 따라 잘 섞어서 잘 사용하면 됩니다.