[Data Structure/자료구조] 배열과 리스트(Array, ArrayList, LinkedList)

Array vs List 차이점

• Array와 List 모두 선형자료구조이지만, Array는 메모리 상에 데이터가 연속적으로 저장되고, List는 메모리 상에 데이터가 비연속적으로 저장된다.
• Array는 선언할 때 크기와 데이터 타입을 지정해야 한다. 대신, 배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있다.
• List는 array처럼크기를 정해주지 않아도 된다. 대신 array에서 index가 중요했다면, List에서는 순서가 중요하다. 하지만, 중간에 데이터를 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재한다.

 

Array vs ArrayList vs LinkedList의 차이점과 특징

• Array는 index로 빠르게 값을 찾는 것이 가능함
• LinkedList는 데이터의 삽입 및 삭제가 빠름
• ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림

+ 사용 분류

• 크기가 가변적인 배열이 필요하다면 ArrayList
• LinkedList의 삭제, 추가 시간 복잡도는 Array나 ArrayList보다 빠르다.
  
  • 즉, 데이터의 삭제 추가가 많을 때 -> LinkedList
  • 데이터의 접근이 많을 때 -> Array, ArrayList
• Array, ArrayList는 인덱스가 있지만 LinkedList(포인터 사용)는 없다.
  • 인덱스가 필요하면 Array, ArrayList를 사용하고,
  • 인덱스가 필요 없다면 LinkedList를 사용하는것이 효율적이다.

 

Array vs ArrayList 차이점

Array

• 사이즈: 초기화시 고정된 사이즈를 가진다.
• 크기변경: 초기화 이후 사이즈 변경은 불가능하다.
• 속도: 초기화시 메모리에 할당되어 ArrayList보다 속도가 빠르다.

ArrayList

• 사이즈: 초기화시 사이즈를 표시하지 않는다. 즉, 크기가 가변적이다.
• 크기변경: 추가, 삭제가 가능하다.
• 속도: 데이터 추가/삭제시 메모리를 재할당하기 때문에 속도가 Array보다 느리다.

 

ArrayList와 LinkedList를 설명하세요.

ArrayList

• ArrayList는 기본적으로 배열을 사용한다. 하지만 일반 배열은 처음에 메모리를 할당할 때 크기를 지정해주어야 하지만, ArrayList는 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다.
• 장점: ArrayList는 각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한번에 가져올 수 있다.
• 단점: 데이터의 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰주어야 한다. 삽입과 삭제가 많다면 ArrayList는 비효율적이다.

LinkedList

• 데이터와 포인터를 담은 노드를 연결시킨, 연결 자료구조다.
• 장점: 순차 자료구조인 배열과 달리 포인터를 사용하기에 삽입과 삭제가 용이하다.
           (일반 배열이나 arrayList에 비해 삽입/삭제가 용이하다.)-> O(1)
           배열과 달리 크기를 동적으로 조절할 수 있는 것도 장점이다.
  
• 단점: 하지만, 링크드 리스트는 특정 노드를 바로 접근할 수 없는 것이 단점이다. -> 특정 노드 검색에 O(n)이 걸린다.
            연결리스트는 임의로 액세스를 허용할 수 없다.
            즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야하기때문에 (이진 검색 수행 불가능) 시간복잡도가 증가하고, 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요하다.
• 종류: 단일연결리스트, 이중연결리스트, 원형연결리스트

➡ 일반 배열(Array)과, LinkedList(연결리스트)를 비교해 주세요.

• 연결리스트는 배열과 달리 포인터를 사용하기에 삽입과 삭제가 유리하다. O(1)의 시간복잡도를 가진다.
• 하지만 index를 사용하는 배열과 달리 특정 노드를 바로 접근할 수 없다는 단점이 있다. 특정 노드 검색에 O(n)의 시간복잡도를 가지게 된다.
• 즉, 검색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다.