배열의 장단점
장점
- 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.
단점
- 크기를 변경할 수 없다.
- 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 한다.
- 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면 메모리가 낭비된다.
- 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
- 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 한다.
- 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.
LinkedList
- 배열과 달리 불연속적으로 존재하는 데이터를 연결(기차처럼 link!)
-
기차칸 하나하나가
Node객체. -
next가 다음요소Node객체를 가리킨다. -
obj: Node에 저장된 데이터 -
삭제 : 한번의 참조변경만으로 가능(
next가 가능케 함) -
추가 : 한번의
Node객체 생성과 두 번의 참조변경만으로 가능
단점
데이터 접근성이 나쁘다.
- 각 노드는 다음 노드객체의 위치만 알지, 다른 노드들의 위치는 모른다.
Doubly LinkedList
-> 개선 : 더블 링크드 리스트doubly linked list : 이중 연결리스트, Node previous를 넣어 이전요소도 접근할 수 있게 접근성 향상, 그래도 여전히 배열보다 접근성 낮음
- 👀👀실제로
LinkedList는 이름과 달리 링크드리스트가 아니라 더블 링크드 리스트로 구현되어 있다??!
-> 더 개선 : 더블리 써큘러 링크드 리스트 doubly circular linked list : 이중 원형 연결리스트, 마지막과 처음을 연결
-
✨ArrayList : 배열기반(연속적) 자료구조
-
✨LinkedList : 연결기반(비연속적) 자료구조
✨ArrayList vs. LinkedList
-
순차적으로 데이터 추가/삭제 속도 : AL 빠름
-
비순차적으로 데이터 추가/삭제 속도 : LL 빠름
-
접근시간(access time), 읽기 : AL 빠름
AL : 비효율적인 메모리 사용
LL : 데이터가 많을수록 접근성이 떨어진다.
