파이썬자료구조(10)이중연결리스트

작성일 | In

강의

목차

  1. 양방향 연결리스트
  2. 스택

양방향 연결리스트.

  • 링크를 양쪽으로 연결

  • 앞으로도 뒤로도 진행 가능

  • Node의 구조를 확장해야한다.
class Node:
    def __init__(self,item):
        self.data = item
        self.prev = None
        self.next = None

양방향 연결 리스트 -> 처음과 끝에 dummy node를 두자.

  • 지난 번, 한 방향으로만 링크가 있었기 때문에, tail에는 더미노드 두지 않았음.
  • 더미노드를 2개 둠으로써, 데이터를 담고 있는 node들은 모두 같은 모양이 된다.
  • 코드를 작성하는게 편안해 진다.
class DoublyLinkedList:
    def __init__(self,item):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

리스트 순회

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

리스트 역순회

def reverse(self):
    result = []
    curr = self.tail
    while curr.prev.prev:
        curr = curr.prev
        result.append(curr.data)
    return result

원소의 삽입

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

특정 원소 얻어내기

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

# 지난 번 코드와 완전히 동일
# 그런데 코드 개선 -> pos<self.nodeCount//2:일 때는 tail에서 찾아가자
def getAt(self,pos):
    if pos < 0 or pos > self.nodeCount:
        return None
    if pos>self.nodeCount//2: # 오른쪽에 있으면 tail부터 찾기
        i = 0
        curr = self.tail
        while i < self.nodeCount - pos +1:
            curr = curr.prev
            i += 1
    else: # 왼쪽에서 있으면 head부터 찾기
        i = 0
        curr = self.head
        while i < pos:
            curr = cur.next
            i+=1
    return curr
# 여전히 리스트의 갯수에 따라 선형시간 알고리즘임은 변함 없다.

이번 강의 - 전체 코드

class Node:

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


class DoublyLinkedList:

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


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


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


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


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


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

연습문제 - 양방향 연결 리스트 메서드 구현

  • def insertBefore(self,next,NewNode)
  • def popAfter(self,porev)
  • def popBefore(self,next)
  • def popAt(self,pos)
  • def concat(self,L)

실습문제 1. reverse() 구현

def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

실습문제 2. 양방향 연결리스트 노드 삽입

def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.next = next
        newNode.prev = prev
        prev.next = newNode
        next.prev = newNode
        self.nodeCount +=1
        return True

실습문제 3. 양방향 연결리스트 노드 삭제

  • popAfter(self,prev) : 인자 prev에 의하여 주어진 node의 다음에 있는 node를 삭제 + 삭제된 node에 담겨 있던 data item 을 리턴
  • popBefore(self,next) : 인자 next에 의하여 주어진 node의 이전에 있던 node를 삭제 + 삭제된 node에 담겨 있던 data item 을 리턴
  • popAt(self,pos) : 인자 pos에 의하여 지정되는 node를 삭제하고 그 node에 담겨있는 dataitem을 리턴하는데, popAfter() 또는 popBefore()를 호출하여 이용하는 방식으로 구현. 인자 pos가 올바른 범위 내에 있지 않을 경우에는 raise IndexError를 이용하여 exception발생
    def popAfter(self, prev):
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        curr.next = None
        curr.prev = None
        self.nodeCount -=1
        return curr.data

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

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

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

    def concat(self, L):
        self.tail.prev.next, L.head.next.prev = L.head.next, self.tail.prev
        self.tail = L.tail # 이 조건 때문에 좀 시간이 걸렸다. tail을 다시 L.tail로 맞춰줘야지!
        self.nodeCount += L.nodeCount

10강 정리 - !!

양방향 리스트에서는 왜 마지막 노드이 거나, 맨 앞 노드일 때, 신경을 안써도 되지? if문을 걸어줄 필요성이 왜 없을까?

맨 앞과 맨 뒤에 실제 데이터를 가지고 있지 않은, dummy head와 tail 노드가 있고, 이들은 삭제의 대상이 아니므로, 모든 노드에 대해서 앞과 뒤에 하나씩의 노드가 위치하는 동일한 모습을 가지고 있기 때문이다.

참고자료 [파이썬_자료구조_알고리즘]https://programmers.co.kr/learn/courses/57

0%