ArrayList와 LinkedList

 

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Binary Tree Zigzag Level Order Traversal - LeetCode

 

리트 코드 데일리 문제를 풀면서, ChatGPT가 알려주는 코드와 내가 작성한 코드의 차이점에 대해 질문함.

 

 

처음과 끝에 원소를 넣고 빼는 작업이 필요할 때, ArrayList를 사용했다. Constant time complexcity가 걸릴 것이라고 생각했기 때문이다.

하지만 ArrayList의 처음에 원소를 넣거나 빼면, 기존의 원소들을 왼쪽 혹은 오른쪽으로 1칸 씩 이동시켜야 하기 때문에 Linear time complecity가 소요된다.

따라서 list의 처음에 원소를 넣거나 빼는 작업을 자주 해야한다면 LinkedList를 사용하는 것이 좋다.
주로 index를 이용해서 특정 원소에 접근하거나, list의 원소 탐색을 자주 한다면(iterate), ArrayList를 사용하는 것이 좋다.

ArrayList는 각 원소를 인접한 메모리에 연속으로 저장하는 반면, LinkedList는 각 원소를 연속성과 무관하게 저장하고 각 원소를 주솟값 참조로 연결한다.

 

 

Q. Why use LinkedList instead of ArrayList? Is there a better advantage? Or just your preferences?

A. The choice between using LinkedList and ArrayList often depends on the specific use case and the performance requirements of the program.

In the context of the Zigzag Level Order Traversal problem on LeetCode, we use a LinkedList to store the nodes at each level. The reason for using LinkedList in this case is that we need to efficiently add and remove elements from both ends of the list. LinkedList provides constant time complexity for these operations, whereas ArrayList provides constant time complexity for random access but linear time complexity for insertions and deletions from the middle or the beginning of the list.

Additionally, LinkedList may consume less memory than ArrayList because it doesn't need to allocate a contiguous block of memory for storing its elements. Instead, each element of a LinkedList is stored in a separate object that contains a reference to the next and previous elements.

So, in summary, the choice between LinkedList and ArrayList depends on the specific use case and the performance requirements. In this problem, we chose LinkedList because we need to efficiently add and remove elements from both ends of the list, and we don't need random access to the elements.

 

Q. At ArrayList, why linear time complexity for insertions and deletions from beginning of the list? I knew it would take Constant time.

A. Insertions and deletions from the beginning of an ArrayList take linear time complexity because ArrayList uses an array internally to store its elements. In order to insert or delete an element at the beginning of the list, all the existing elements need to be shifted one position to the right or left, respectively. This operation takes linear time, as the number of elements that need to be shifted increases linearly with the size of the array.

On the other hand, LinkedList stores its elements in a linked list data structure, where each element points to the next one in the list. Insertions and deletions from the beginning of a linked list can be done in constant time, as they only involve changing the pointers of the first element to point to the new first element or the second element, respectively.

Therefore, if you frequently need to insert or delete elements from the beginning of a list, using a LinkedList can be more efficient than an ArrayList. However, if you mainly need to access elements by their index or iterate over the list, an ArrayList may be more efficient.