배열(array)과 연결리스트(linked list) 차이점

배열(array)

 

배열은 같은 타입의 변수들로 이루어진 집합으로 메모리의 연속공간에 값이 채워져 있는 형태

 

장점

 - 검색 성능 : 인덱스를 사용하여 원소에 바로 접근이 가능(O(1))

 - 읽기.쓰기, 즉 참조에 좋은 성능

 - 데이터양과 상관없이 항상 일정한 연산량을 갖는 알고리즘

 

단점

 - 초기 선언된 사이즈만큼 메모리의 연속 공간이 필요하므로 작은 빈 공간은 버려지는 경우가 생겨 메모리 활용에 비효율적

 - 값의 삽임과 삭제에서 비효율적, 데이터 중간 지점에서 자료의 삽입, 삭제가 일어날 경우 다음 항목의 모든 값을 이동시켜야 함

 

 

연결 리스트(Linked list)

 

배열의 단점을 보완하기 위하여 만들어짐.

 - 데이터를 분산해서 저장하고, 연결해주자!

 

장점 

 - 선언할 때 크기를 지정하지 않으며 주소로 계속 연결하여 연속된 공간이 필요하지 않아 빈 공간을 활용할 수 있음

각 요소를 분산해서 메모리에 저장을 하고 각 요소에 다음 값의 주소를 알면 해결!

 - 각 요소가 다음 요소의 주소를 알고있어 값을 추가/삭제하는 속도가 배열에 비해 빠름

 

단점

 - 특정 원소로 바로 접근이 불가

 - 첫 번째 주소(Head)부터 차례대로 순차 접근해야 한다.

 

 

배열 / 연결리스트 정리

 

그렇다면 언제 배열을 쓰고, 언제 연결리스트를 써야 할까?

	배열(array)	연결리스트(linked list)
크기	고정	동적
주소	연속	불연속
데이터 참조	O(1)	O(n)
삽입과 삭제	O(n)	O(n)

 

배열 데이터 수가 자주 바뀌지 않고 참조가 자주 일어난다면 배열,

데이터 삽입과 삭제가 자주 일어난다면 연결리스트