[Kotlin] 자료구조 1 (배열, 스택, 큐, 링크드리스트)

[Java] array(배열)과 arrayList(리스트)의 차이(arrayList는 어떻게 동적으로 늘어나는가?)

연결 리스트

장점: 중간 지점의 아이템 추가 삭제가 빠르다.

단점: 데이터 접근이 느리다.

• head 부터 순회 해야 하므로 O(N) 의 시간 복잡도를 갖는다.

크기 변경: 가능

메모리 사용량: 각 노드는 데이터 외에도 포인터를 저장해야 하므로 메모리 사용량이 더 크다.

시간 복잡도:

• 접근: Sequential Access - O(N)
• 추가, 삭제:
  • 맨 앞 또는 뒤: O(1)
  • 중간 위치:
    • 삽입 할려는 곳의 index를 모를경우 : O(N)
    • 삽입 할려는 곳의 index를 알 경우: O(1)

종류: