연결 리스트 (Linked List) - 더미 노드 추가

연결 리스트가 힘을 발휘할 때

최대 장점 삽입/삭제가 유연하다는 것이다. 하지만 작성한 코드를 보면 n번째에 있는 노드를 찾아서 삽입/삭제가 이루어지기 때문에 처음부터 값을 찾아가기가 부담스러워서 간단한 일은 아니다. 그래서 이러한 부담을 줄이기 위해 조금 다른 구조의 메서드를 만든다.

• insertAfter(prev, newNode)
• popAfter(prev)

어떤 노드를 주고 그 뒤에 있는 노드를 삽입 삭제할 수 있도록 정의를 한 메서드이다. 하지만 맨 앞에서 어떻게 처리해야할지 에 대한문제가 생기기 때문에 맨앞에 dummy node를 추가한 형태로 조금 변형된 연결 리스트를 만들었다.

더미 노드에 0번을 붙인다.

 

 

 

 

 

 

조금 변형된 연결 리스트

# LinkedList 클래스
class LinkedList:
    # 생성자
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

연결 리스트의 생성자를 변경

 

 

 

 

 

 

리스트 순회

    # 리스트 순회
    def traverse(self):
        result = []
        curr = self.head
        # 현재 노드의 next가 존재하는 동안 반복
        while curr.next:
            result.append(curr.data)
            curr = curr.next
        return result

 

 

 

 

 

k번째 원소 얻어내기

더미 노드를 추가했으니 에러지점과 시작점을 변경해주어야한다. getAt(0) -> head

    # 특정 원소 참조
    def getAt(self, pos):
        # 더미노드가 추가되었으니 0미만이거나 노드개수보다 많으면 에러 (getAt(0) -> head)
        if pos < 0 or pos > self.nodeCount:
            return None
        
        i = 0 # 더미노드가 추가되었으니 0부터 시작
        curr = self.head # 연결리스트의 첫번째 노드를 가르킴
        
        # i가 pos보다 작은 동안에 i를 하나씩 증가시키면서 curr를 curr의 next를 가르키게 한다
        while i < pos: 
            curr = curr.next
            i += 1
        
        return curr

 

 

 

 

 

원소의 삽입

def insertAfter(self, prev, newNode)

노드 prev가 하나 주어지고 삽입하려는 노드 newNode가 주어진다. prev가 가리키는 node의 다음에 newNode를 삽입하고 성공/실패에 따라 True/False를 리턴한다.

 

 

원소의 삽입 흐름

처음 상태

newNode.next = prev.next

prev.next = NewNode

 

 

맨 끝에 노드를 추가하는 경우를 고려해주어야한다.

링크도 조절해야하지만 tail도 조절해줘야한다.

    # 원소의 삽입
    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        # 맨 뒤에 삽입을 하는 경우라면 tail도 조정해줘야함
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True

 

 

 

메서드 insertAt()의 구현

이미 구현한 insertAfter()를 호출하여 이용하는 것으로

1. pos 범위 조건 확인
2. pos == 1인 경우에는 head 뒤에 새 node 삽입
3. pos == nodeCount + 1 (맨 끝)인 경우에는 prev <- tail
4. 그렇지 않은(맨 끝이 아닌) 경우에는 하나하나 찾아야한다. prev <- getAt(...)

 

    # 새로운 원소의 삽입
    def newInsertAt(self, pos, newNode):
        # 범위 유효성 확인
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        
        # pos 가 1일때는 빈 공간에 삽입하는 경우니까 tail을 넣어주면 안된다. 
        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        
        else:
            prev = self.getAt(pos-1)
        
        return self.insertAfter(prev, newNode)

 

 

 

 

 

원소의 삭제

def popAfter(self, prev):

prev의 다음 node를 삭제하고 그 node의 data를 리턴

 

 

원소의 삭제 흐름

처음 상태

링크 조정 후 curr꺼내서 리턴

 

 

원소의 삭제 코드 구현 주의사항

1. prev가 마지막 node 일 때 (prev.next == None)

• 삭제할 node없음
• return None

2. 리스트 맨 끝 node를 삭제할 때 (curr.next == None)

• tail 조정 필요

 

 

popAfter() 구현

    def popAfter(self, prev):
        # prev다음에 노드가 없는 경우 삭제할 노드가 없으니 None 리턴
        if prev.next == None:
            return None
            
        # 삭제하려는 노드를 curr에 담기
        curr = prev.next
        
        # 삭제할 노드가 없는 경우
        if curr.next == None:
            # 유일한 노드일 때
            if self.nodeCount == 1:
                self.tail = None
            # 유일한 노드가 아닐 때
            else:
                self.tail = prev
        
        # 링크 조정
        prev.next = curr.next
        self.nodeCount -= 1
        return curr.data

 

popAt() 구현

    def newPopAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos-1)
        return self.popAfter(prev) 

 

 

 

 

 

 

두 리스트의 연결

처음상태

 

    # 두 리스트의 연결
    def concat(self, L):
        # 원래 리스트의 맨 끝이 이어붙이려는 리스트의 처음으로
        self.tail.next = L.head.next
        # 리스트 L이 비어있을 경우
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount