Array List와 Linked List

Linked List

Linked List는 위와 같이 양방향 연결 리스트로 구성되어 있습니다.

Linked List는 인덱스를 통해 접근하지 않고 head로 부터 탐색하기 때문에 O(n)의 시간이 걸립니다.

 

삽입

Linked List의 삽입 시 연결된 주소만 바꿔주면 됩니다. 이때 가장 앞 또는 끝이 아닌 중간에 데이터를 삽입할 경우 해당 인덱스의 데이터를 검색하기에 O(n)의 시간 복잡도가 걸립니다. 오직 삽입은 O(1)의 시간 복잡도를 가집니다.

 

삭제

삭제 또한 연결된 주소를 다음 주소로 바꿔주기만 하면 됩니다. 삽입과 마찬가지로 해당 인덱스의 데이터를 검색하여 O(n)의 시간 복잡도가 걸립니다. 오직 삭제는 O(1)의 시간 복잡도를 가집니다.

Array List

Array List는 위와 같이 해당 인덱스에 값이 위치합니다.

검색 시 인덱스를 통해 바로 접근하기에 O(1)의 시간 복잡도를 가집니다.

 

삽입

삽입 시 만약 초기 설정한 (default 10)이 넘는다면 기존 배열보다 더 큰 배열로 복사하여 공간을 늘립니다. 그 후 삽입할 위치 뒤의 데이터들을 밀어줍니다. 삽입할 위치에 데이터를 넣어줍니다. 데이터를 밀어주는 작업이 있기 때문에 O(n)의 시간 복잡도를 가집니다.

 

삭제

삭제할 데이터가 위치한 데이터를 삭제한 후 그 뒤의 데이터들을 앞으로 당겨줍니다. 위와 마찬가지로 O(n)의 시간 복잡도를 가집니다.

 

언제 뭐를 써야할까?

 

1) 검색이 잦은 경우 Array List가 적합합니다. Linked List는 순차적으로 검색하여 찾지만 Array List는 인덱스를 통해 바로 접근할 수 있기 때문입니다.

 

순차적으로 접근해야한다며?

그래도 Array List가 더 빠릅니다. Array List는 메모리에 연속되어 저장되지만 Linked List는 무작위의 공간에 저장됩니다. 그렇기에 추가적으로 다음 데이터의 주소를 찾은 후 접근하기 보다 메모리상 연속적으로 저장된 Array List가 더 빠릅니다.

 

2) 추가, 삭제가 많은 경우 Linked List가 더 적합합니다. Linked List는 데이터의 위치를 색인하는 속도를 제외한다면 O(n)의 속도로 추가 및 삭제를 할 수 있습니다.

 

색인 속도를 포함한다면?

색인 속도를 포함해도 Linked List가 더 빠릅니다. Linked List는 데이터의 다음 주소만 바꿔주면 되지만 Array List는 추가 공간을 확보하거나 데이터를 밀어주고 당겨주는 처리 속도가 느리기 때문입니다.