[List] 단순 연결 리스트, Singly Linked List

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 단순 연결 리스트 (Singly Linked List)

• 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조
• 메모리 할당을 받아 노드(Node)를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결
• 삽입이나 삭제 시 항목들의 이동이 필요 없음, 빈 공간이 없음
• 자료를 탐색하기 위하여 순차 탐색(Sequential Search)가 필요
• 맨 앞의 노드를 Head라 칭함

  ※ 자료구조로서의 단순 연결 리스트는 노드의 구조체임 (노드는 자료)

 

- 연산

• 탐색 : 타겟을 매개변수로 받아 탐색에 성공할 때까지 순차적으로 탐색, 실패할 경우 None 반환
• 삽입
  • Insert front : 리스트의 맨 앞(Head)에 새 노드 삽입
  • Insert after : 매개변수로 주어진 노드 다음에 새 노드 삽입
  • Insert last : 리스트의 마지막(Tail)에 새 노드 삽입
• 삭제
  • Delete front : 리스트의 맨 앞의 노드 삭제
  • Delete after : 매개변수로 주어진 노드 다음을 삭제
  • Delete last : 리스트의 마지막의 노드 삭제

 

- 수행 시간

• 탐색은 연결 리스트의 노드들을 첫 노드부터 순차적으로 방문해야 하므로 O(n) 소요
• 삽입과 삭제는 각각 O(1) 개의 레퍼런스만을 갱신하므로 O(1) 소요 (단, Insert after나 Delete after의 경우에 특정 노드의 레퍼런스가 주어지지 않으면 Head로부터 노드를 찾기 위하여 탐색을 수행하므로 O(n) 소요)
• Tail 정보를 단일 연결 리스트가 갖고 있다면 삽입과 삭제가 O(1) 소요 (정보가 없다면 순차 탐색이 필요하므로 O(n) 소요)