파이썬 | 링크드 리스트(Linked List) 구조, Big O - 1

링크드 리스트는 데이터를 저장하는 선형 데이터 구조로, 노드(Node)로 구성되어 있습니다. 각 노드는 데이터와 다음 노드에 대한 참조(포인터)를 포함하고 있어, 데이터의 삽입과 삭제가 용이한 특징을 가지고 있습니다.

 

링크드 리스트의 구조

링크드 리스트는 기본적으로 두 가지 구성 요소로 이루어져 있습니다:

1. 노드(Node): 각 노드는 두 가지 정보를 담고 있습니다.
   • 데이터(Data): 실제 저장하고자 하는 값입니다.
   • 다음 노드에 대한 포인터(Next): 다음 노드를 가리키는 참조입니다.
2. 헤드(Head): 링크드 리스트의 시작점을 가리키는 포인터입니다. 헤드를 통해 리스트에 접근할 수 있습니다.
3. 테일(Tail): 링크드 리스트의 마지막 노드를 가리키는 포인터입니다. 링크드 리스트의 끝을 나타내며, 일반적으로 테일은 다음 노드에 대한 포인터가 None으로 설정되어 있습니다.

https://medium.com/@singhamritpal49/singly-linked-list-3d59153506ae

링크드 리스트와 메모리 스페이스

1. 동적 메모리 할당: 링크드 리스트는 노드가 필요할 때마다 동적으로 메모리를 할당받아 사용합니다. 이 때문에 사전에 필요한 메모리 크기를 정해놓을 필요가 없습니다.
2. 노드 구조: 각 노드는 두 가지 정보를 가지고 있습니다.
   • 데이터: 실제 저장할 값.
   • 포인터: 다음 노드를 가리키는 참조. 이로 인해 각 노드는 메모리 상에서 서로 떨어져 있어도 연결될 수 있습니다.

https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d

 

BIg O

삽입 (Insertion)

• 꼬리(Tail) 삽입: O(n) (일반적인 경우)
  • 테일 포인터가 없는 링크드 리스트에서는 리스트의 끝에 추가하기 위해 전체 노드를 탐색해야 하므로 O(n)입니다. 그러나 테일 포인터가 있는 경우 O(1)로 수행할 수 있습니다.

 

1. 새로운 노드 생성: 새로운 노드를 메모리에서 생성합니다.
2. 테일 포인터 사용: 테일 포인터를 사용하여 현재 마지막 노드에 접근합니다.
3. 연결: 현재 마지막 노드의 next 포인터를 새로 생성한 노드로 설정합니다.
4. 테일 포인터 업데이트: 테일 포인터를 새 노드로 업데이트합니다.

이 과정에서 리스트의 길이에 관계없이 각 단계가 상수 시간에 수행되기 때문에 전체 삽입 작업은 O(1)의 시간 복잡도를 가집니다.

• 머리(Head) 삽입: O(1)
  • 리스트의 맨 앞에 새로운 노드를 추가하는 경우, 기존의 헤드를 새 노드의 다음 포인터로 설정하고 헤드를 새 노드로 업데이트하면 됩니다.

 

1. 새로운 노드 생성: 새로운 노드를 메모리에서 생성합니다. 이 단계는 항상 일정한 시간에 수행됩니다.
2. 새 노드의 포인터 설정: 새로운 노드의 next 포인터를 현재의 헤드 노드로 설정합니다. 즉, 새로운 노드가 기존의 첫 번째 노드를 가리키게 합니다.
3. 헤드 포인터 업데이트: 리스트의 헤드 포인터를 새로운 노드로 업데이트합니다. 이렇게 하면 새로운 노드가 리스트의 첫 번째 노드가 됩니다.

이 모든 단계는 리스트의 길이에 관계없이 항상 동일한 시간에 수행되기 때문에, 머리 노드를 삽입하는 작업은 O(1)로 간주됩니다. 리스트의 크기가 커져도 수행 시간은 변하지 않습니다.

 

• 중간 삽입: O(n)
  • 특정 위치에 노드를 삽입하려면 해당 위치까지 탐색해야 하므로 O(n) 시간이 소요됩니다.

 

 

• 위치 탐색: 중간에 삽입할 위치를 찾기 위해 리스트를 처음부터 끝까지 탐색해야 합니다. 이 과정은 삽입하고자 하는 위치까지의 노드를 하나씩 방문해야 하므로, 최악의 경우 O(n) 시간이 걸립니다.
• 새로운 노드 생성: 삽입할 위치를 찾은 후, 새로운 노드를 메모리에서 생성합니다. 이 단계는 상수 시간 O(1)에 수행됩니다.
• 포인터 업데이트:
  • 새로운 노드의 next 포인터를 현재 노드의 next 포인터로 설정합니다.
  • 이전 노드의 next 포인터를 새로운 노드로 업데이트합니다.

리스트의 길이에 따라 위치 탐색 시간이 달라지므로, 중간 삽입은 O(n)의 시간 복잡도를 가지게 됩니다. 리스트의 크기가 커질수록 탐색에 소요되는 시간도 증가합니다.

 

삭제 (Deletion)

• 꼬리(Tail) 삭제: O(n)
  • 마지막 노드 찾기: 리스트에서 마지막 노드를 삭제하려면, 해당 노드에 접근해야 합니다. 이 경우 마지막 노드는 그 이전 노드의 next 포인터가 None인 노드입니다.
  • 전달 포인터 필요: 마지막 노드에 접근하기 위해서는 마지막 노드의 이전 노드를 찾아야 합니다. 이를 위해 리스트를 처음부터 끝까지 탐색해야 하므로, 리스트의 길이에 비례하는 시간이 소요됩니다.
  • 연결 업데이트: 마지막 노드를 찾은 후, 그 이전 노드의 next 포인터를 None으로 설정하여 리스트에서 마지막 노드를 끊어줘야 합니다.
  • 이 과정이 O(n) 시간 복잡도를 발생시킵니다

• 머리(Head) 삭제: O(1)
  • 헤드 노드 참조: 현재의 헤드 노드를 가리키는 포인터를 참조합니다. 이 노드가 삭제될 것입니다.
  • 헤드 포인터 업데이트: 헤드 포인터를 다음 노드로 업데이트합니다. 즉, 현재 헤드 노드의 next 포인터가 가리키는 노드를 새로운 헤드로 설정합니다.
  • 메모리 해제: (언어에 따라 다름) 삭제할 헤드 노드를 메모리에서 해제합니다. 파이썬에서는 가비지 컬렉션이 이를 처리하므로, 명시적으로 메모리 해제를 할 필요는 없습니다.
  • 이 모든 단계는 리스트의 크기에 관계없이 상수 시간 내에 완료되기 때문에, 머리 노드를 삭제하는 작업은 O(1)로 간주됩니다. 리스트의 길이에 상관없이 항상 동일한 작업을 수행하기 때문입니다.
• 중간 삭제: O(n)
  • 위치 탐색: 삭제할 노드의 위치를 찾기 위해 리스트를 처음부터 끝까지 탐색해야 합니다. 이 과정에서 삭제하고자 하는 노드를 찾기 위해 노드를 하나씩 방문해야 하므로, 최악의 경우 O(n) 시간이 걸립니다.
  • 포인터 업데이트:
    • 삭제할 노드를 찾은 후, 이전 노드의 next 포인터를 삭제할 노드의 next 포인터로 업데이트합니다. 이렇게 하면 삭제할 노드를 리스트에서 제거하게 됩니다.
  • 메모리 해제: 삭제할 노드를 메모리에서 해제합니다. 파이썬에서는 가비지 컬렉션이 이를 처리하므로, 명시적으로 메모리 해제를 할 필요는 없습니다.
  • 리스트의 길이에 따라 위치 탐색 시간이 달라지므로, 중간 삭제는 O(n)의 시간 복잡도를 가집니다. 리스트의 크기가 커질수록 탐색에 소요되는 시간도 증가합니다.

탐색 (Search)

• 탐색: O(n)
  • 특정 값을 찾기 위해 리스트의 시작부터 끝까지 순차적으로 탐색해야 하므로 O(n) 시간이 소요됩니다.

---

다음 포스팅에서 이어집니다.