7. 연결 리스트 2

• 원소의 삽입
• 원소의 삭제
• 두 리스트 합치기

원소의 삽입

코드 구현 주의 사항
(1) 사입하려는 위치가 리스트 맨 앞일 때
prev 없음
Head 조정 필요
(2) 삽입 하려는 위치가 리스트 맨 끝일 때
Tail 조정 필요
(3) 삽입 하려는 리스트가 빈 리스트인 경우

def insertAt(self, pos, newNone)
    # pos가 옳바른 위치에 잇는가
    if pos <1 or pos > self.nodeCount + 1:
        return False
    # 첫 위치에 삽입하는 경우
    if pos == 1:
        newNode.next = self.head
        self.head = newNode
    else:
        if pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        newNode.next = prev.next
        prev.next = newNode
   # 삽입하련느 위치가 끝인 경우
   if pos == self.nodeCount + 1:
        self.tail = newNonde
       self.nodeCount += 1
    return True

연결 리스트 원소 삽입의 복잡도

• 맨앞에 삽입하는 경우: O(1)
• 중간에 삽입하는 경우: O(n)
• 맨 끝에 삽입하는 경우 : O(1) / tail을 가지고 있기때문

연결 리스트 연산 - 원소의 삭제

: pos가 가리키는 위치의 node를 삭제하고 그 node의 데이터를 리턴

코드 구현 주의 사항

• 삭제하려는 node가 맨 앞의 것일 때
  • prev 없음
  • Head 조정 필요
• 리스트 맨 끝의 node를 삭제할 때
  • Tail 조정 필요
• 유일한 노드를 삭제할 경우

코드 구현하기 - 숙제

def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        if pos == 1:
            curr = self.head
            self.head = self.head.next
            if self.nodeCount == 1:
                self.tail = None
                self.head = None
            data = curr.data
        else:
            if pos == self.nodeCount:
                prev = self.getAt(pos - 1)
                data = prev.next.data
                prev.next = None
                self.tail = prev
            else:
                prev = self.getAt(pos - 1)
                curr = prev.next
                next_ = curr.next
                prev.next = next_
                data = curr.data
        self.nodeCount -= 1
        
        return data

연결 리스트 원소 삭제의 복잡도

• 맨앞에서 삭제하는 경우: O(1)
• 중간에서 삭제하는 경우: O(n)
• 맨 끝에서 삭제하는 경우 : O(n)

연결 리스트 연산 - 두 리스트의 연결

def concat(self.L):
    self.tail.next = L.head
    if L.tail:
        self.tail = L.tail
    self.node Count == L.nodeCount

연결 리스트 장점
: 삽입과 삭제를 자연스럽게 할 수있다.