[Programmers] 3. 기본 자료구조: 연결리스트(Linked List) (2): 더미노드 추가

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

---

자료구조 2. 연결리스트 (Linked List) (2)

더미 노드 (dummy) 를 추가한 연결리스트 만들기

• 삽입/삭제를 할 때 삭제할 노드의 이전 노드를 주고서 다음 노드를 삭제한다면 더 쉽고 바르게 삭제를 할 수 있습니다.
• 따라서, 삽입할 때는 insertAt(pos)을 insertAfter(prev, newNode)과 insertAt(pos, newNode)으로 나누고,
• 삭제할 때는 popAt(pos)을 popAfter(prev)와 popAt(pos)로 나눕니다.
• 맨 앞 노드의 처리를 쉽게 만들기 위해 맨 앞에 더미노드를 추가합니다.

---

Python에서 연결리스트 Class로 구현

• 초기 Class

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None

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

연결리스트의 연산 구현

1. k 번째 원소 참조

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None
    i = 0
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1
    return curr

• 맨 앞 더미노드가 생겼기 때문에 i를 0으로 초기화 합니다.

2. 리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr.next:
        curr = curr.next
        result.append(curr.data)
    return result

• while의 반복문에서 현재 노드의 다음 노드가 있으면 반복문을 실행하고, result 배열에 담는 것으로 변경됩니다.

3. 길이 얻어내기

def getLength(self):
    return self.nodeCount

4. 원소 삽입

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:
        return False

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

• insertAt()은 pos의 유효성 검사만 하고, 유효하다면 이전 노드(prev)를 찾아 insertAfter()를 호출하여 새로운 노드를 삽입합니다.

5. 원소 삭제

def popAfter(self, prev):
    if prev.next is None:
        return None
    curr = prev.next
    prev.next = curr.next

    if curr.next is None:
        self.tail = prev
    self.nodeCount -= 1
    return curr.data

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

• popAt()도 삽입할 때와 마찬가지로 pos의 유효성 검사를 하고, 유효하다면 이전 노드(prev)를 찾아 popAfter()를 호출하여 노드를 삭제합니다.

6. 두 리스트 합치기

def concat(self, L):
    self.tail.next = L.head.next
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount

---

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.