Linked List(연결 리스트)

Linked List(연결 리스트)

---

특징

• 노드가 연결되어 있는 형태의 자료구조다.
  • 노드 : 데이터 + 다음 노드를 가리키는 포인터
• 연속되지 않은 메모리 공간에 저장(+동적 할당)

 

시간복잡도

• 접근 / 탐색 : O(N)
  • 첫 번째 노드부터 (N-1)번을 거쳐 가야 한다.
• 삽입 / 삭제 : 단순 삭입/삭제 : O(1),  but 현실적으로 O(N)
  • 단순하게 연결된 구조만 변경하면 된다.
  • 그러나, 원하는 위치에 삽입/삭제 하기위해서는 접근, 탐색의 과정이 필요하다.
    • 따라서, O(1 + N - 1) ⇒ O(N)이 된다.

 

배열(Array)과의 차이

• 배열과 달리 크기에 제한이 없어 삭제/추가 작업이 자유롭다.
• 배열에 비해 접근, 탐색에 시간이 오래걸린다.
  • 배열의 접근,탐색 시간복잡도 : O(1)

 

 

참고

---

간략 설명! 배열(Array)과 연결 리스트(Linked List)에 대해서 알아보자! - 차이점과 시간복잡도, 활용