python 알고리즘용 LinkedList

강의를 들었던 내용을 기반으로 이전에 간단하게 링크드리스트를 만들었었는데,

 

그 리스트는 단방향이라 노드 삭제하는 메소드를 만들기도 번거롭고, 알고리즘에 사용하기에도 부적합해서

양방향으로 다시 링크드리스트를 만들었다.

 

 

전체 코드

 

class Node():

    def __init__(self, data=None):
        self.next = None
        self.prev = None # .prev 추가로 각 노드를 이전 노드와도 연결
        self.data = data


class List():
    head = None
    tail = None # tail 노드 추가로 head와 tail을 각각 관리

    def __init__(self, data=None): # 생성자가 실행될 때 head와 tail이 동일한 노드를 가리킴
        self.head = Node(data)
        self.tail = self.head

    def append(self, data): # 리스트 끝부분에 노드 추가

        if self.head is None:
            self.__init__(data)

            return

        elif self.head.next is None: # head.next가 없을때, 즉 노드가 하나일 때의 조건
            self.head.next = Node(data)
            self.tail = self.head.next
            self.tail.prev = self.head

            return
            

        self.tail.next = Node(data) # 리스트를 처음부터 돌지 않고 테일로 바로 이동하여 처리
        self.tail.next.prev = self.tail
        self.tail = self.tail.next

        return

    def deleteLastNode(self):

        if self.head is None:
            return None

        elif self.head.next is None:
            self.head = None
            self.tail = None
            return

        self.tail = self.tail.prev
        self.tail.next = None

        return
        
    def printAllNodes(self):

        if self.head is None:
            print('리스트가 비어있음')
            return

        curr = self.head
        print('######printAllNodes#######')

        while curr.next is not None:

            print(curr.data)

            curr = curr.next

        print(curr.data)
        print('##########################')

        return

 

이전의 단방향과 달라진 점은

Node 클래스에 prev 필드를 추가해서 각 노드들이 prev를 통해 이전 노드로도 이동이 가능하게 한 것, 

List 클래스에 tail 필드를 추가해서 노드 추가나 삭제를 할 때 리스트를 처음부터 돌리지 않고 끝부분으로 바로 이동할 수 있도록 한 것.

 

정렬 알고리즘 TIL에 써먹을려고 다시 짜놨다.

그래서 getNode, addNode 등 필요하지 않은 자잘한 함수들은 일단 배제하고 구성!