이중 연결 리스트(Doubly linked list)_출력

김지수·2021년 4월 16일
0

Data Structure

목록 보기
8/15
post-thumbnail

코드

#이중 링크드 리스트
class DLinkedList:

    #D_L_list에서 쓸 노드
    class Node:
        def __init__(self, v, n = None, p = None):
            self.value = v #저장된 데이터
            self.next = n #다음 노드 가리키는 변수
            self.prev = p #이전 노드 가리키는 변수

    #D_L_List에서 필요한 변수
    def __init__(self):
        self.head = None #첫 생성시 내부에는 노드가 없음
        self.tail = None

    #head로 삽입. v : 데이터
    def insertNodeBefore(self, v):
        #없을 경우
        if self.head is None:
            self.head = self.Node(v)
            self.tail = self.head #같은 노드를 가리킴
            print(self.head.value)
        else:
            #self.head : 기존노드, self.head.prev : 기존노드의 prev
            self.head.prev = self.Node(v,n=self.head) #1,2번을 동시수행
            #self.head.prev : 기존노드의 prev == 새로운 노드
            self.head = self.head.prev #3. head를 새로운 노드로 변경

    #tail로 삽입. v : 데이터
    def insertNodeAfter(self, v):
        #없을 경우
        if self.tail is None:
            self.tail = self.Node(v)
            self.head = self.tail #같은 노드를 가리킴
        else:
            #self.tail : 기존노드, self.tail.next : 기존 노드의 next
            self.tail.next = self.Node(v,p=self.tail) #1,2번을 동시수행
            #self.tail.next : 기존노드의 next == 새로운 노드
            self.tail = self.tail.next #3. tail를 새로운 노드로 변경

    def printNodeBefore(self):
        #데이터가 없을 때
        if self.head is None:
            print("저장된 데이터가 없음")
            return
        else:
            print("<현재 리스트 구조>", end='\t')
            link = self.head #처음은 head를 지정. 이후부터는 현 노드의 next를 지정

            #link가 가리키는 노드가 없을 때까지 반복
            #None,0,""는 조건판단에서 False 처리, 그 외는 True로 처리
            while link :
                print(link.value, '<->' , end = ' ')
                link = link.next #link를 현 위치 노드의 next로 변경
            print() #줄바꿈 용

    def printNodeAfter(self):
        #데이터가 없을 때
        if self.tail is None:
            print("저장된 데이터가 없음")
            return
        else:
            print("<현재 리스트 구조>", end='\t')
            link = self.tail

            while link :
                print(link.value, '<->' , end = ' ')
                link = link.prev #link를 현 위치 노드의 next로 변경
            print() #줄바꿈 용


##테스트
if __name__=="__main__":
    dl = DLinkedList()
    dl.printNodeBefore()
    dl.insertNodeBefore('1st')  # head삽입 테스트
    dl.printNodeBefore()
    dl.insertNodeBefore('2nd')  # head삽입 테스트
    dl.insertNodeAfter('3rd')  # tail삽입 테스트
    dl.insertNodeAfter('4rd')  # tail삽입 테스트
    dl.printNodeBefore()
    dl.printNodeAfter()

결과

저장된 데이터가 없음
1st
<현재 리스트 구조> 2nd <-> 1st <-> 3rd <-> 4rd <->
<현재 리스트 구조> 4rd <-> 3rd <-> 1st <-> 2nd <->


설명

저장된 노드가 없을 때

'저장된 데이터가 없음' 출력

저장된 노드가 있을 때(head에서부터 출력)

head가 가리키는 Node의 value 출력한 후, 변수 next가 None이 아니면 next를 통해 다음 노드로 이동하여 value를 출력함
이 과정을 next가 None일 때까지 반복함

저장된 노드가 있을 때(tail에서부터 출력)

tail이 가리키는 Node의 value 출력한 후, 변수 prev가 None이 아니면 prev를 통해 다음 노드로 이동하여 value를 출력함
이 과정을 prev가 None일 때까지 반복함
뒤에서부터 출력하므로 head로 할 때와는 반대 결과가 출력됨


참고
https://wikidocs.net/34532

profile
A Data human as a Learner, a Supporter, and a Listener

0개의 댓글