ArrayList
ArrayList는 연속된 메모리 공간에 저장된 데이터의 집합이다.
연속된 메모리 공간에 저장되어있기 때문에 cpu cache의 이점을 이용할 수 있다.
add
데이터가 add될 때 할당된 메모리 공간에 데이터를 넣다가 할당된 공간이 모자라게 될 경우
더 큰 메모리 공간을 다시 할당해서 지금까지 저장된 데이터를 옮긴 후 다시 데이터를 add합니다.
remove
데이터를 삭제할 경우 삭제된 공간 이후에 저장된 모든 데이터를 왼쪽으로 한 칸씩 shift합니다.
insert(데이터, 인덱스)
특정 위치에 데이터를 insert하고 싶은 경우 특정 위치 이후의 데이터를 오른쪽으로 한 칸씩 shift합니다.
LinkedList
LinkedList는 node의 집합으로 이루어져 있으며 node는 value와 다음 node의 주소값으로 이루어져 있다.
node는 다음 node의 주소값을 알고 있을 필요가 없기 때문에 각기 다른 메모리 공간에 저장되어있다.
(따라서 CPU cache의 이점을 이용할 수 없다.)
LinkedList는 head와 tail을 가지고 있다.(singly linked list)
doubly linked list
circular linked list
doubly circular linked list
등 종류도 다양한다. doubly의 경우 다음 node 뿐만 아니라 이전 node의 주소값도 알고 있다.
add
tail로 설정된 노드 뒤에 새로운 노드를 추가한다. 새롭게 추가된 노드가 tail이 되고 기존 tail이었던 노드의 주소값으로 새롭게 추가된 노드가 들어가도록 한다.
remove
head부터 차근차근 삭제하고자 하는 데이터를 찾아서 조회 후 데이터를 찾으면 삭제한다.
이때 삭제하고자 하는 노드의 이전 노드의 주소값을 삭제하려고 하는 노드의 다음 주소값으로 연결해준다.
insert
데이터 조회 후 해당하는 노드 사이에 끼워넣는다.
이때 이전 노드의 주소값은 추가하고자 하는 노드로 변경하고 추가하는 노드의 주소값은 다음 노드로 변경한다.
두 가지 비교
ArrayList의 경우 데이터 삭제, insert에서 shift가 발생하기도 하고 데이터 add 시 공간을 새롭게 할당해야하는 등의 단점이 존재하지만
성능 개선이 이루어졌고 무엇보다 LinkedList를 만든 사람도 LinkedList를 안 쓴다고 하니까
진짜..! 이상한 상황이 아니라면 ArrayList를 사용하자.
'알고리즘' 카테고리의 다른 글
| [leetcode] Toeplitz Matrix (0) | 2022.10.31 |
|---|---|
| [leetcode] Roman to Int (1) | 2022.10.14 |
| [leetcode] Two Sum (0) | 2022.10.13 |
| [프로그래머스] 이진 변환 반복하기 (0) | 2022.09.11 |
| [프로그래머스] JadenCase 문자열 만들기 (0) | 2022.09.11 |