Array(배열)와 Linkedlist(연결리스트)의 차이점은?
해당 Post는 Array(배열)와 Linkedlist(연결리스트)의 차이점를 정리한 파일이다.
Array(배열)은 무엇인가?
데이터가 많아지면 그룹 관리의 필요성이 생긴다. 이럴 때 프로그래밍에서 사용하는 것이 배열
여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조
장점
데이터의 참조가 쉽다.
즉, 인덱스값을 기준으로 어디든 한번에 참조 가능
단점
크기가 고정되어 있다. 사용하기 전에 배열 크기를 지정해야 한다.)
동적 배열로 해결이 가능하다. (배열이 꽉 차면 두 배씩 크기 늘리기)
메모리를 한 덩어리로 차지하므로, 배열 크기가 클 경우 배열 전체를 위한 메모리를 할당받지 못하는 경우가 있다.
삽입이 복잡하다.
배열 중간에 항목을 추가하려면 우선 기존 항목을 밀어내고 해당 공간을 비워야 한다. 따라서 최대 N번의 항목 이동이 발생한다. (N은 항목의 갯수)
Linkedlist(연결리스트)는 무엇인가?
리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취한 데이터 스트럭쳐
리스트 자료구조의 핵심은 엘리먼트들 간의 순서.
따라서 리스트를 다른 말로는 시퀀스(sequence) 라고도 부른다. 즉 순서가 있는 데이터의 모임이 리스트이다.
장점
크기가 유동적이다
메모리 중간에 삽입/삭제가 자유롭다.
단점
단점
항목 접근이 오래 걸린다.
첫 항목부터 순차적으로 접근하므로 최대 O(n)의 시간이 걸린다.
물리적으로 인접한 메모리에 위치해있지 않다.
배열의 항목은 물리적으로 인접해있어 접근 시간 단축과 캐싱에 유리하다고 한다. 하지만 연결리스트는 아니다.
참조 포인터를 위한 메모리 공간이 낭비된다.
정리
배열 : 데이터의 크기가 정해져있고, 추가적인 삽입 삭제가 일어나지 않으며, 검색을 필요로 할 때 유리하다.
리스트 : 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리하다.
C의 경우
리스트를 지원하지 않는다. 대신 배열을 지원한다.
리스트를 사용하려면 직접 만들거나 라이브러리를 사용해야한다. (따라서 리스트에 대한 깊은 이해와 안목이 필요함)
Java의 경우
Array와 ArrayList / LinkedList가 지원이 된다.
배열은 배열의 장점이, 리스트는 리스트의 장점이 있기 때문에 개발자가 원하는대로 직접 선택가능하다.
인덱스를 이용해서 데이터를 가져오는 것이 빈번하다면 내부적으로 배열을 이용하는 ArrayList가 훨씬 빠르다.
하지만 데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적이다.
