배열과 연결리스트 (Array & Linked list)

배열

배열을 사용하는 경우, 원소를 메모리에 차례대로 붙여서 저장한다. 만약 원소가 추가되거나 하면 전체 배열이 함께 저장될 수 있는 다른 공간으로 이동하게 될 텐데, 배열의 크기를 사전에 정해 미리 해당 공간만큼을 확보하여 해결 할 수 있다.

• 모든 원소의 주소를 알고 있다. 특정 원소값을 찾을시 효율적이다.
• 원소가 지정된 배열크기 보다 적다면 메모리를 낭비할 수 있다
• 배열에 들어가야 할 원소가 더 늘어난다면 어차피 배열의 모든 원소는 메모리상에서의 자리를 옮겨야한다.
• 임의 접근(random access)방식. 읽기 속도가 빠르다.

연결리스트

연결리스트 사용시 각 원소마다 다음 원소에 대한 주소가 저장되어 있어서 메모리의 어느 곳에나 둘 수 있다. (여러 임의의 메모리 주소들이 하나의 목록으로 연결되어 있는 것)

• 연결리스트에서 마지막 원소를 보고 싶을시 바로 볼 수가 없다. (주소를 바로 알 수 없기 때문). 원소들끼리 메모리상에서 이웃하고 있지 않기 때문에 특정한 원소만 알고 싶을시 효율이 떨어진다.
• 순차 접근(sequential access)만 가능

배열 VS 리스트 실행시간 비교

리스트는 이전 원소가 가리키는 값만 변경하면 되므로 중간 삽입과 삭제가 쉽다. 배열은 다음에 오는 모든 원소의 위치를 바꿔야하며, 삽입으로 인해 공간이 부족할 시 모든 원소를 새로운 장소로 복사해야하기 때문에 이 경우 효율이 떨어진다.

배열의 읽기 속도가 빠른것은 임의 접근 방식이기 때문이다. 그래서 리스트보다 배열을 사용하는 경우가 더 많다.

연결 리스트는 삽입과 삭제에 좋고, 배열은 임의 접근에 좋다.

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘