[자료구조] LinkedList vs ArrayList

LinkedList와 ArrayList는 같은 List라는 이름을 달고 있지만 data 구조나 장단점에서 확연한 차이를 보인다. LinkedList에 대해 정리해보며 ArrayList와는 어떤 차이가 있는지 정리해보았다.

LinkedList

https://www.geeksforgeeks.org/data-structures/linked-list/

각 노드가 데이터와 다음 노드의 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 데이터가 물리적, 논리적으로 연결되어 있는 배열 리스트와는 다르게 연결 리스트는 데이터가 논리적으로만 연결 되어있다.

 

ArrayList

https://mson-it.tistory.com/3

[자료구조] Array vs ArrayList

 

Performance

	LinkedList	ArrayList
Search	O(n)	O(n)
Append	O(1)	O(1)
Insertion	O(1)	O(n)
Delete(맨 앞)	O(1)	O(1)
Delete	O(1)	O(n)
Access	O(n)	O(1)

• Insert 나 delete 시에 뒤에 있는 data들을 한칸식 이동해야 하는 ArrayList와는 다르게 LinkedList는 그 전 노드의 next pointer만 바꿔주면 됩니다. (O(1)).
• LinkedList는 ArrayList보다 insert 와 delete 부분에서 빠르고 data를 조회하는 부분에선 느린 속도를 보입니다. 그래서 조회가 많이 안 일어나고 data의 삽입과 삭제가 많이 일어나는 상황에서 LinkedList를 많이 사용합니다. 

물론 이는 Indexing이 잘 되어 있었을 때를 가정합니다. 만약 그렇지 않다면 실제 insert나 delete가 수행될 때 그 전 index에 access 하기 위한 O(n) 이 소비됩니다. 

 

Resize

• 최초에 capacity를 정해놓는 ArrayList와는 다르게 LinkedList는 data가 삽입되거나 삭제될 때 포인터를 통해 새로운 노드를 연결하거나 해당 노드의 연결을 끊어주기만 하면 되기 때문에 Resize가 별도로 이루어지지 않습니다. 
• Capacity와 실제 size 사이에서 memory 낭비를 가지는 ArrayList보다 LinkedList는 memory를 효율적으로 사용가능합니다.

 

Reference

https://yongkis.tistory.com/22

https://stackoverflow.com/questions/840648/why-is-inserting-in-the-middle-of-a-linked-list-o1