[Python] 연결 리스트(Linked List) 구현

📌 노드(Node) 구현

• 연결 리스트(Linked List)는 각 노드(Node)가 한 줄로 연결되어 있는 자료 구조이다.
• 노드(Node)는 데이터값(Data)과 다음 혹은 이전 노드(Node)의 연결 정보를 가지고 있는 Link(Next)로 구성되어 있다.

• 그러므로 연결 리스트(Linked List)를 구현하기 위해서는 노드(Node)를 먼저 구현해야 한다.

class Node:
    def __init__(self, item):
        self.data = item   #node의 Data
        self.next = None   #node의 Link

📌 연결 리스트(Linked List) 구조 및 구현

• Head: 연결 리스트 시작. 알아야 하는 리스트를 찾아가기 위해 필수적으로 필요하다.
• Tail: 연결 리스트의 끝. 삽입 및 삭제를 할 위치가 리스트의 맨끝일 때 걸리는 시간을 줄여 줄 수 있다.
• node의 수: 연결 리스트 내 실제 가지고 있는 데이터 요소의 개수. 삭제하거나 탐색할 때 사용 가능하다.
  

class LinkedList:
    def __init__(self):
        self.nodeCount = 0  #node의 수
        self.head = None  
        self.tail = None

📌 연결 리스트(Linked List) 연산 구현

1) 특정 원소 참조

• k 번째 노드를 찾아가는 함수 (노드 전체를 return)

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount: # 찾고자 하는 pos가 연결 리스트 범위에서 벗어난 경우
            return None  # None을 리턴 (찾을 수 없으므로)
        i = 1
        curr = self.head   # 그게 아니라면 head를 현재 위치로 설정
        while i < pos: 	   # 찾고자 하는 pos 번째까지 next를 통해 노드 이동
            curr = curr.next
            i += 1
        return curr  #함수를 통해 찾은 pos 번째의 노드 반환

• 배열과의 효율 비교

2) 리스트 순회

• 리스트의 처음부터 끝까지 순회하는 함수 (모든 노드의 값을 return)

    def traverse(self):
        node = []   #모든 노드의 값을 담기 위한 리스트
        curr = self.head 
        
        # while curr.next:  #curr.next가 있을 때로 설정해 주어도 됨
        while curr != None:   #curr가 연결 리스트 범위에서 벗어나면 None이 되므로 None이 될 때까지 순환
            node.append(curr.data)  #node의 data 값을 리스트에 추가
            curr = curr.next		#다음 node로 이동
        return node

3) 길이 찾기

• 리스트의 길이 찾기

    def getLength(self):
        return self.nodeCount  #이미 nodeCount를 가지고 있기 때문에 nodeCount return

4) 특정 위치의 원소 삽입

구현 시 주의할 점
1. 삽입하려는 위치가 리스트의 제일 처음일 때
	- Prev 없음
    - Head를 조정해야 함
2. 삽입하려는 위치가 리스트의 제일 끝일 때
	- Tail 조정해야 함
3. 빈 리스트에 삽입할 때
	- 1, 2 두 조건을 모두 만족해야 함

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:  # pos의 위치가 리스트를 벗어날 경우
            return False

        if pos == 1:   # 삽입하고자 하는 위치가 제일 처음인 경우 
            newNode.next = self.head  
            self.head = newNode		 # head의 위치를 조정해야 함

        else:
            if pos == self.nodeCount + 1:   # 삽입하고자 하는 위치가 제일 마지막인 경우
                prev = self.tail 			# tail의 위치를 조정해야 함
            else:
                prev = self.getAt(pos - 1)  # getAt을 통해 찾고자 하는 노드 prev(이전) 노드를 찾음
            newNode.next = prev.next        
            prev.next = newNode 			# prev->newNode->prev.next가 되도록 해 줌

        if pos == self.nodeCount + 1:		#이때 pos의 위치가 제일 마지막이었다면 tail을 삽입된 노드로 바꿔 주어야 함
            self.tail = newNode

        self.nodeCount += 1					#node를 삽입하여 하나가 늘었으므로 node의 개수를 1 증가
        return True

• 연결 리스트 원소 삽입의 복잡도
  • 맨앞: O(1)
  • 중간: O(n)
  • 맨끝: O(1) -> tail 포인터를 가지고 있지 않으면 최악의 시간 복잡도가 나오지만 tail을 가지고 있어 상수 시간이 소요됨

5) 특정 위치의 원소 삭제

구현 시 주의할 점
1. 삭제하려는 노드가 맨앞일 때
	- prev 없음
    - Head 조정해야 함
2. 리스트 맨끝의 노드를 삭제할 때
 	- Tail 조정해야 함
3. 유일한 노드를 삭제할 때
	- 1, 2, 두 조건에 의해 처리되는가?

    def popAt(self, pos):
        #index에 벗어나면 index 에러 발생
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        #삭제해야 하는 노드가 맨앞(head)일 때
        if pos == 1:
            curr = self.head
            self.head = curr.next
            #리스트에 원소가 하나밖에 없을 때의 처리 필요
            if pos == self.nodeCount:
                self.tail = self.head
                
        else:
            prev = self.getAt(pos - 1)
            curr = prev.next
            prev.next = curr.next
            #tail 조정 필요
            if pos == self.nodeCount:
                self.tail = prev
                
        self.nodeCount -= 1
        return curr.data

• 연결 리스트 원소 삭제 복잡도
  • 맨앞: O(1)
  • 중간: O(n)
  • 맨끝: O(n) (삭제하려는 노드가 마지막 노드일 때 즉, pos == nodeCount인 경우 prev를 찾을 방법이 없어서 앞에서부터 조회해야 함.)
    -> 이 문제를 해결하기 위해 이중 연결 리스트를 많이 사용함

6) 두 리스트 합치기

구현 시 주의 사항
1. 인자 L이 비어 있다면 L.tail이 유효한 경우에만 코드가 유효하도록 해야 함.

    def concat(self, L):
      self.tail.next = L.head.next
      if L.tail:   #L.tail이 유효하다면
          self.tail = L.tail
      self.nodeCount += L.nodeCount  

📌 Dummy Head를 가지는 연결 리스트(Linked List) 구조 및 구현

• Head: 연결 리스트의 시작. dummy node
• Tail: 연결 리스트의 끝.
• node의 수
  

class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

📌 Dummy Head를 가지는 연결 리스트(Linked List) 연산 구현

1) 특정 위치의 원소 삽입

구현 시 주의 사항
1. tail의 뒤에 새로운 노드를 삽입하는 경우: tail도 새로운 노드를 가리키도록 옮겨 주어야 함.
2. insertAfter()을 구현 후 insertAt() 구현 시 호출 

    def insertAfter(self, prev, newNode):
       newNode.next = prev.next
       if prev.next is None:
           self.tail = newNode
       prev.next = newNode
       self.nodeCount += 1
       return True


   def insertAt(self, pos, newNode):
       if pos < 1 or pos > self.nodeCount + 1:  #pos의 범위 확인 
           return False

       if pos != 1 and pos == self.nodeCount + 1:  #pos== nodeCount+1인 경우 prev <- tail
           prev = self.tail
       else:  
           prev = self.getAt(pos - 1)
       return self.insertAfter(prev, newNode)

2) 특정 위치의 원소 삭제

구현 시 주의 사항
1. prev가 마지막 노드일 때 prev.next == None
	- 삭제할 노드가 없으면 None을 return
2. 리스트 맨끝의 노드를 삭제할 때 (curr.next == None)
	- tail 조정

    def popAfter(self, prev):
      #prev가 마지막 노드일 때에 대한 처리
      if prev.next == None:
          return None
      
      curr = prev.next
      #curr가 마지막 노드일 때에 대한 처리
      if curr.next == None:
          self.tail = prev
      
      prev.next = curr.next
      self.nodeCount -= 1
      return curr.data

  def popAt(self, pos):
      #index에 벗어나면 index 에러 발생
      if pos < 0 or pos > self.nodeCount:
          raise IndexError  
      
      prev = self.getAt(pos - 1)
      return self.popAfter(prev)