01939 중량제한 문제를 풀다가 생긴 시간초과에서 궁금증이 생김.
Node class를 따로 생성하여 bfs를 진행했는데 LinkedList를 사용했을 때는 시간초과가 생겼던 문제가 ArrayList를 사용했을 때 없어짐.
BFS에서의 LinkedList 쓰임
BFS에서의 LinkedList<Integer>[] adjList가 주로 사용되는데, 어떤 노드가 서로 연결되어 있는지를 확인하기 위해 주로 사용됨.
그리고 문제를 해결하기 위해선 값이 입력된 adjList[i]를 각각 Collection.sort() 해줘야 함.
이는 ‘순서대로 검색하기’ 위해 거쳐야 하는 작업임.
LinkedList vs ArrayList
[출처 : http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html]
LinkedList는 각 원소마다 앞, 뒤 원소의 위치값을 가지고 있고, ArrayList에는 index가 존재함.
그렇기 때문에 ArrayList의 경우 get(idx)를 사용하여 바로 검색할 수 있지만, 순서가 존재하는 LinkedList의 경우 처음부터 차례대로 검색해야 한다는 단점이 있음.
ArrayList
기본적으로 배열을 사용하지만, 처음 메모리를 할당할 때 크기를 지정해줘야 하는 배열과는 달리 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제가 가능함.
위에서 언급한 대로 get(idx)를 통해 무작위 접근이 가능하기 때문에, 검색에서 유용함.
하지만 삽입이나 삭제의 경우 idx 조정이 필요하므로 삽입이나 삭제가 많으면 비효율적임.
LinkedList
내부적으로 양방향의 연결 리스트로 구성되어 있어 참조하려는 원소에 따라 처음부터 정방향 또는 역순으로 순회가 가능함.
순차적 접근이라서 index를 사용하는 ArrayList 보다는 검색 부분에서 비효율적이지만,
데이터를 추가하거나 삭제할 때 가리키고 있는 주소값만 변경해주면 되기 때문에 ArrayList에 비해 상당히 효율적임.
⇒ 조회가 빈번한 작업에서는 ArrayList를, 추가나 삭제가 빈번한 작업에서는 LinkedList를 사용하는 것이 좋음.
[참고 자료]
https://www.holaxprogramming.com/2014/02/12/java-list-interface/
https://dev-coco.tistory.com/19
