ArrayList와 LinkedList

ArrayList와 LinkedList는 자바에서 가장 많이 사용하는 배열의 형태이다.

 

• ArrayList :  데이터의 저장순서가 유지되고 중복을 허용함.
• LinkedList : 링크드 리스트는 불연속적으로 존재하는 데이터들의 주소값들을 연결한 형태로 구현됨.

 

 

데이터의 삭제  -  ArrayList

삭제한 후 데이터들을 다시 연결하기 위해 한 칸씩 당기는 작업이 필요

 

만약에 0 1 2 3 4라는 배열에서 2이라는 값이 사라진다면 0 1 3 4의 순서를 맞추기 위해 arr[3], arr[4]를 arr[2], arr[3]으로 이동시키는 작업이 필요

 

실제로 System.arrycopy(data, index+1, data, index, size-index-1) 라는 로직이 ArrayList에서 작동됨

 

위의 예제에서는 System.arrycopy(data, 3, data, 2, 2)로 작동됨.

---> data[3]에서 data[2]로 2개의 데이터를 복사하라는 뜻

 

 

 

데이터의 삭제  -  LinkedList

데이터를 삭제할 때에는 이전의 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경해주면 된다.

 

사진 출처 : Java의 정석 (남궁성)

링크드 리스트는 단방향이기 때문에 다음 요소에서 이전 요소의 값을 알기 어렵다.

 

더블 링크드 리스트는 참조변수를 하나 더 추가하여 다음 요소와 이전 요소의 참조 값을 둘 다 알 수 있도록 한다.

 

실제로 자바에서 LinkedList 클래스는 더블 링크드 리스트로 구현되어 있다고 하는데, 이는 싱글 링크드 리스트의 접근성이 낮아서 그것을 보완하기 위함이라고 한다.

 

 

 

 

두 리스트의 비교

 

데이터를 추가하는 것도 삭제와 비슷하다. 링크드 리스트는 추가하는 위치의 양 옆 요소의 참조값을 변경해주면 되고, ArrayList는 데이터를 하나씩 밀면 되는 것이다.

 

위 문자에서 유추할 수 있듯이 순차적으로 추가, 삭제하는 것은 ArrayList가 LinkedList보다 빠르다. 그냥 데이터를 넣기만 하면 되는 것이기 때문이다.

 

하지만 배열의 중간에 추가하거나 삭제할 경우에는 ArrayList는 데이터를 계속해서 변경해줘야 하기 때문에 양 옆 요소의 참조값만 변경해주면 되는 LinkedList가 실행속도가 더 빠르다.

 

또한 데이터에 접근 (읽기) 속도는 ArrayList가 더 빠르다.

 

그 이유는 LinkedList는 불연속적으로 위치한 요소들이 연결되어 있기 때문에 맨 앞이나 맨 뒤에서부터 순차적으로 데이터를 따라가야만 접근할 수 있기 때문이다.

 

 

 

결론

데이터 개수가 변하지 않으면 ArrayList가 좋음

데이터 개수의 변경이 많을 것으로 예상되면 LinkedList가 좋음

 

데이터 접근에는 ArrayList가 LinkedList보다 빠름

 

데이터 추가, 삭제는 LinkedList가 ArrayList보다 빠름  -----  중간에 추가

(단, 중간에 추가, 삭제가 아니라 순차적으로 추가 삭제하는 것은 LinkedList가 빠름)

 

 

 

결론을 참고하여 각 상황에 맞는 배열을 골라서 사용하는 것이 효율적이다.