[자료구조] ArrayList 와 LinkedList

자료구조 연결리스트(Array)와 단일연결리스트(LinkedList)에 대해 알아보자

---

두 자료구조의 차이점은 index의 유무라고 말할 수 있습니다. ArrayList에는 index가 존재하고 LinkedList에는 존재하지 않는다.

 

그림을 통해 알아봅시다.

 

ArrayList의 빨간 글이 index이다. index로부터 객체를 참조할 수 있습니다. 반면 LinkedList에는 index가 존재하지 않기 때문에 4번째 값을 참조하기 위해서는 0번째 객체를 타고 1번째 > 2번째 > 3번째 > 4번째 방식으로 참조할 수 있습니다. 데이터를 조회하기에는 index로 접근하는 것이 효율적입니다.

 

그렇다면 삽입,삭제는 어떨까?

 

위의 그림과 비교해보자 만약 index 2를 제거한다면 3번째부터 마지막 객체에 접근해 index를 하나씩 당겨줘야 한다. 삽입도 마찬가지 2번째에 삽입한다면 3번째부터 마지막 객체에 접근해서 index를 하나씩 늘려줘야 한다.

 

LinkedList에서는 2번째 객체를 제거하고 싶을 땐 1번째에서 2번째를 가리키는 주소값을 3번째 객체로 변경해 주면 된다. 주소값을 수정하는 것으로 삽입, 삭제를 수행할 수 있습니다. 물론 제거한 객체가 가리키는 주소값은 null로 변경해줘야 합니다.

 

결론

ArrayList는 조회에 좋은 성능을 가지고 있고, LinkedList는 삽입, 삭제에 유리한 자료구조입니다.