[자료구조] 배열 & 연결 리스트 & 이중 연결 리스트 비교

💡 리스트 종류: 배열, 연결 리스트, 이중 연결 리스트

🌈 연결 리스트 (Linked List)

🌈 이중 연결 리스트 (Double Linked List)

• prev 포인터 때문에 linked List 보다 더 많은 메모리가 필요
  

🍄 배열(Array) & 연결 리스트(Linked List) 시간복잡도 비교

추가

• Array: 맨 끝에 추가하는 경우 O(1), 배열이 가득 차있을 경우 배열 사이즈 재할당한 후 데이터를 옮기기 때문에 O(N)

검색

• Linked list: 인덱스 정보가 없기 때문에 노드를 통해 이동 → O(N)
• Array: 인덱스로 접근 가능 → O(1)

데이터의 접근, 탐색이 중요하다면 배열을 쓰고,
데이터의 추가, 삭제가 중요하다면 연결 리스트를 쓰자!

🍄 이중 연결 리스트 시간복잡도

추가: O(1)

• Tail 노드의 prev 포인터를 이용

인덱스를 통한 검색: O(N)

• Head 또는 Tail 노드를 이용할 수 있기 때문에 정확하게는 O(2/N)
  

인덱스를 통한 삽입: O(N)

• Head 또는 Tail 노드를 이용

노드를 찾을 때는 이중 연결 리스트가 단일 연결리스트보다 시간을 절반으로 줄일 수 있으므로 더 낫다.
이 외의 이중 연결 리스트의 시간복잡도는 단일 연결 리스트의 성능과 같다.