LinkedList와 ArrayList 차이에 대해서 설명해주세요.

[Seobway23]

Linked List

불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있습니다.

특징

• 공간의 제약이 존재하지 않습니다.
• 삽입, 삭제 처리 속도가 빠릅니다.
• 특정 자료의 탐색 시간이 많이 소요됩니다. (요소를 get하는 과정에서 순차접근만 가능)

Array List

자료를 연속적인 묶음으로 저장합니다.

특징

• 모든 데이터를 상수 시간으로 접근 가능합니다.
• 공간이 부족하다면 리사이징이 필요합니다.

[kimmainsain]

답변

Array, List의 차이

• Array는 메모리 상에 데이터가 연속적으로 저장되고, 고정된 크기를 갖는다는 특징을 가지고 있습니다. (삽입 삭제 O(n), index O(1))
• List는 메모리 상에 데이터가 비연속적으로 저장됩니다. 크기를 정해주지 않아도 된다는 특징을 가지고 있으며 데이터 삽입 및 삭제하는 데 동작은 O(1)이지만, 특정 데이터를 찾기위해 O(N)이 소모되기에 결과적으로 O(N)의 시간복잡도를 갖는 특징이 있습니다.

ArrayList, LinkedList의 차이

• LinkedList는 한 노드가 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있기에 데이터의 삽입과 삭제에 용이합니다.
• ArrayList는 index를 가지고 있기에 검색할 때에 용이합니다.

[SunheeYoon96]

답변

ArrayList

• 논리적 저장순서와 물리적 저장 순서가 일치하는 자료구조로, 인덱스를 통해 데이터에 접근하므로 조회에 있어서 LinkedList 보다 빠르다는 이점이 있습니다.
• 반면에 삽입,삭제는 인덱스의 순서를 모두 옮겨야하기에 LinkedList보다 느릴 수 있습니다.

LinkedList

• 논리적 저장순서와 물리적 저장순서가 일치하지 않는 양방향 연결리스트 자료구조로, 각 원소들은 데이터와 그 다음 연결된 원소의 참조 주소를 값으로 가집니다.
• 그래서 주소 값을 바꾸는 것만으로 삽입과 삭제가 가능합니다.
• 그러나 원하는 원소에 접근하기 위해서는 처음부터 순회를 해야합니다.

[freakFlow]

답변

LinkedList는 요소간의 주소를 가르키는 포인터를 이용해 리스트를 구현한 것이고, ArrayList는 배열을 이용해 구현한 리스트입니다. LinkedList의 경우 요소의 삽입과 삭제에 용이하고, ArrayList의 경우 순회에 용이하다는 차이점이 있습니다.