LinkedList, ArrayList?

<img alt="pasteImage.png" pathname="PCIO6Z190223204030.PNG" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/PCIO6Z190223204030.PNG" style="border-style:solid; border-width:0px; width:400px" title="pasteImage.png" />

<br/>

자바 컬렉션 중 LinkedList, ArraryList가 있습니다.

List 인터페이스를 구현하였으므로, List로 업캐스팅이 가능합니다.

둘의 차이점을 알 필요가 있을거 같습니다.

<br/>

<br/>

<hr />
<br/>

LinkedList는 다음과 같습니다.

명칭과 같이 연결 링크를 이용합니다. 값을 가지고 있고 다음 노드를 가리키는 포인터를 가집니다.

<br/>

**A -> B -> C **같은 구조 입니다.

A는 B를 가리키는, B는 C를 가리키는 포인터를 가지고 있습니다.

<br/>

그럼 삽입/삭제 연산은 어떨까요.

B를 삭제하면

A -> C 로 구조가 바뀝니다. 단순히 A가 C 노드를 가리키게 하면 쉽게 처리됩니다.

그럼 D를 A와 C사이에 넣는다면,

**A -> D -> C 구조로 바뀝니다. **A가 D를 가리키고, D가 C를 가리키면 됩니다.

즉 삽입/삭제가 상대적으로 쉽습니다.

<br/>

그럼 검색은 어떨까요..?

**A -> B -> C-> D-> E -> ~~ ->Z **구조에서 K번째 값을 찾는다면 어떻게 해야할까요.

A부터 시작해서 가리키는 노드를 차근 차근 따라가며 K번째 값을 찾아야 합니다.

<br/>

<hr />
<br/>

ArrayList는 다음과 같습니다.

명칭에 따라, 내부적으로 배열을 이용한 리스트입니다.

예를들어, 배열안에 **A B C D **가 나란히 있는 구조입니다.

<br/>

그럼 삭제 연산은 어떨까요?

B를 삭제 한다면

A NULL C D 가 되고 ,

B자리에 C를 C자리에 D를 옮겨야 A C D 로 완성됩니다.

<br/>

그럼 삽입 연산은 어떨까요?

A 와 B 사이에 K를 넣는다면,

B자리에 K가 들어가고, B C D는 한칸씩 뒤로 옮겨야겠죠.

그래야 A K B C D가 완성됩니다.

<br/>

또한 배열은 고정적인 길이를 가집니다.

삽입을 계속하면, 내부적으로 더 긴 배열을 가지도록 재조정 연산을 수행합니다.

즉 ArrayList는 삽입/삭제에 비효율적입니다.

<br/>

검색은 어떨까요. K번째의 값을 찾을때 입니다.

내부적으로 배열이기때문에 인덱스값만 안다면, 쉽게 찾을 수 있습니다.

bigO(1) 시간복잡도로 바로 찾을 수 있습니다.

<br/>

<hr />
<br/>

사실 학부시절에 다 배운 내용임에도 불구하고, 개발과정에서는 두 컬렉션을 구분없이 쓸때가 많습니다.

반성하고 좀 더 효율적인 코딩이 될 수 있도록 공부해봅니다..?

<br/>

<br/>

<br/>

참고

<a href="http://www.nextree.co.kr/p6506/">http://www.nextree.co.kr/p6506/</a>

<br/>