ArrayList와 LinkedList

ArrayList

---

 

ArrayList란?

---

• Java의 Collection Framework에서 가장 많이 사용되는 Collection Class
• 배열같이 인덱스를 통해 인자를 관리한다는 특징이 있지만 배열과는 다르게 크기가 동적으로 할당됨
  기본 저장용량은 10이며, 10을 넘어가면 1.5배씩 증가
  정확히 설명하자면, 기존 ArrayList의 크기가 동적으로 변하는 것이 아니라 기존 저장용량을 넘어서면 기존 ArrayList의 저장용량보다 1.5배 큰 ArrayList를 만들고, 이 리스트에 기존 ArrayList의 값들을 복사하는 것
• 값이 하나 삭제되면 해당 인덱스 뒤의 모든 인자가 한 칸씩 당겨지고, 값이 하나 추가되면 해당 인덱스 뒤의 모든 인자가 한 칸씩 밀림
• Generic을 이용해 타입 안정성을 제공함
• 모든 기본 타입형과 Object를 담을 수 있는 배열과는 다르게 ArrayList는 Object element 담을 수 있음

ArrayList 데이터 추가 과정

 

장점

---

• 인덱스를 통해 특정 요소에 빠르게 접근 가능
• 데이터 추가와 삭제 용이

 

단점

---

• 요소를 추가/삭제 할 경우 모든 요소의 위치가 이동하기 때문에 연산이 많아짐

 

 

 

LinkedList

---

 

LinkedList란?

---

• 각 요소들간의 위치 정보를 통한 연결(link)로 구현된 객체
• 각 요소들은 다음 요소의 위치 정보, 즉 포인터를 가지고 있음
• 현재 위치의 이전, 다음 위치만 가지고 있기 때문에 데이터 추가와 삭제 용이
  추가 데이터 노드를 만들어주고 원하는 위치 이전 데이터의 포인터를 수정해준 뒤, 추가 데이터의 포인터를 다음 데이터의 위치로 설정
• 불연속적으로 메모리를 활용함

LinkedList 데이터 추가 과정

 

장점

---

• 불연속적으로 메모리를 활용하기 때문에 메모리 관리와 재사용 용이
• 포인터만 수정해주면 되기 때문에 데이터 추가 및 삭제 용이

 

단점

---

• 순차탐색 방식을 사용하기 때문에 탐색 속도가 느림
  랜덤 접근이 허용되지 않고 탐색 시 무조건 head부터 탐색해야 하기 때문
  같은 이유로 이진탐색을 수행할 때에도 LinkedList는 적합하지 않다
• 포인터를 저장해놓아야 하기 때문에 추가적인 메모리를 필요로 함
• Cache Hit Ratio가 낮음

 

 

 

ArrayList와 LinkedList 비교

---

 

 

 

참고

---

https://onlyfor-me-blog.tistory.com/249

[JAVA] ArrayList 사용법 정리

https://github.com/Songwonseok/CS-Study/blob/main/DataStructure/Array&ArrayList&LinkedList.md

GitHub - Songwonseok/CS-Study: 면접 대비 CS 스터디(+알고리즘)

https://doublesprogramming.tistory.com/161

자바 - 컬렉션프레임워크 : ArrayList

https://arabiannight.tistory.com/63

자바/Java ArrayList<T> 제네릭스(Generics)란?

https://escapefromcoding.tistory.com/130

List ( ArrayList & LinkedList )