✨ ArrayList
인덱스로 객체를 관리하고, 크기를 동적으로 늘릴 수 있는 자료구조
리스트인데 Array의 성격을 가지고 있는 리스트이다.
그렇다면 어떠한 특성이 있을까??
✅ ArrayList를 쓰는 이유
-
인덱스를 통해 빠르게 접근하고자 할 때
: 인덱스를 사용하기 때문에 인덱스를 활용하여 요소를 찾고자 할 때 빠르게 찾을 수 있다. -
배열과 달리 가변적으로 데이터 저장 공간을 늘리거나 줄이려고 할 때
: 크기가 고정되어있는 배열과 다르게 ArrayList는 유동적으로 변경할 수 있다.
😒 ArrayList를 쓰지 않는 이유
-
배열의 공간이 꽉 찰 때마다 배열을 늘리는 과정에서 지연이 발생
: 배열을 copy => copy한 배열을 늘림 => 리턴 -
삽입, 삭제 시 느림
: 요소들의 위치를 앞뒤로 자동으로 이동시키기 때문이다.
ArrayList에 데이터를 삽입하고 삭제하는 것은 줄을 서는 곳에서 중간에 한명이 끼어들기를 하거나 나가버릴 때 자리를 채우고, 자리를 뒤로 양보하는 것과 같다.
조금 더 직관적인 예를 들어서 ArrayList를 설명하고 LinkedList와 비교해보겠다.
ArrayList는 복도형 아파트에 친구들이 모두 사는 것을 의미한다.
이 친구들은 상당히 친하기 때문에 무슨 일이 있던지 간에 붙어서 살아야한다.
친구들이 따닥따닥 붙어 살기 때문에 호수만 알면 친구집을 찾아가기 편하다.
하지만 누구하나가 이사를 간다면 관련된 모든 집이 이사를 가야한다.
반대로 누구하나가 이사를 온다면 관련된 모든 집이 이사를 가야한다.
LinkedList는 층별 아파트에 친구들이 모두 사는 것을 의미한다.
맨 아래층에 사는 사람은 그 다음 층에 사는 친구의 호수를 안다.
친구들 중 누구 하나를 찾으려고 하려면 맨 아래층부터 시작해서 위층으로 찾을 때 까지 찾아다녀야 한다.
하지만 누구하나가 이사를 가도 호수와 연락처만 전달해주면 된다.
누구하나가 이사를 와도 앞집이 호수를 알아가고 뒷집에 호수를 알려준다.
✨ LinkedList
메모리 상에 흩어져있는 노드들이 연결되어있는 자료구조
어떠한 기능과 동작(Operation)으로 이루어져 있는 지 알아볼 필요가 있다.
-
HEAD : 첫번째 노드는 어떤 노드인가에 대한 정보
-
NODE : OOD에서는 하나의 객체로 구성, DataField와 Link Field를 가지고 있음
-
Data Field : 말 그대로 데이터를 가지고 있는 NODE의 한 부분
-
Link Field : 다음 노드에 대한 정보가 들어있는 NODE의 한 부분, next를 통해서 연결
✅ LinkedList를 쓰는 이유
- 데이터 추가와 삭제가 빠름
: 데이터 구조의 틀을 바꿀 필요가 없음 (배열의 크기를 정하거나 그럴 필요가 없음)
😒 LinkedList를 쓰지 않는 이유
-
탐색이 느림
: 배열과 달리 데이터에 무작위 접근이 불가능, 첫번째 노드부터 순차적으로만 접근해야 함 -
많은 메모리 사용
: 각 노드는 포인터 (다음 노드를 지칭, Link Field의 역할)를 담고 있기 때문
✅ 연결 리스트의 유형
-
단일 연결리스트 : 노드는 하나의 포인터 만(LinkField)을 가짐, 오른쪽 찌르기
-
이중 연결리스트 : 노드는 2개의 포인터(LinkField)를 가짐, 양쪽 찌르기
-
원형 연결리스트 : 마지막 노드가 첫 노드를 가리킴, 보드게임 순서 정하기
