[알고리즘 강의] 파트9. 연결 리스트(Linked Lists) (3)

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

- 삽입과 삭제가 유연하다는 것이 가장 큰 장점

- 그런데 잠깐, 지난번에 구현한 코드는 삽입과 삭제에 효율적이지 못함

 

지난번 코드

삽입과 삭제가 유연하다는 장점을 살리기 위해 새로운 메서드들을 만들자:

- insertAfter(prev, newNode)-> 근데 맨 앞에는 어떻게?

- popAfter(prev) -> 근데 맨 앞에서는 어떻게?

 

해결 방법: 조금 변형된 연결 리스트

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

연산 정의

1. 길이 얻어내기

2. 리스트 순회

3. 특정 원소 참조(k번째)

4. 원소 삽입

5. 원소 삭제

6. 두 리스트 합치기

 

연결 리스트 연산 - 리스트 순회

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

 

연결 리스트 연산 - k번째 원소 얻어내기

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

 

연결 리스트 연산 - 원소의 삽입

def insertAfter(self, prev, newNode):

1) prev가 가리키는 node의 다음에

2) newNode를 삽입하고

3) 성공/실패에 따라 True/False를 리턴

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

매서드 inserAt()의 구현

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

def insertAt(self, pos, newNode):

 

(1) pos 범위 조건 확인

(2) pos == 1인 경우에는 head 뒤에 새 node 삽입

(3) pos == nodeCount + 1 인 경우는 prev <- tail

(4) 그렇지 않은 경우에는 prev <- getAt(...) 

 

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)

 

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

def popAfter(self, prev):

1) prev의 다음 node를 삭제하고

2) 그 node의 data를 리턴

코드 구현 주의사항

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

-> 삭제할 node 없음

-> return None

 

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

-> Tail 조정 필요

 

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

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

 

실습 과제 - dummy head 를 가지는 연결 리스트 노드 삭제 (popAfter(), popAt() 구현하기)

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


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


    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


    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)


    def popAfter(self, prev):
        if prev.next == None:
            return None
        curr = prev.next
        prev.next = curr.next        
        if curr.next == None:
            self.tail = prev            
        self.nodeCount-=1
        return curr.data
            

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

def solution(x):
    return 0

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.