이중 연결 리스트

단일 연결 리스트는 단방향(head쪽)으로 밖에 삽입, 삭제, 조회를 못하는 반면

이중 연결 리스트는 양방향 이동을 구현하므로써 다음 노드와 이전 노드의 이동이 가능하도록 구성되어있다. 때문에 노드에 변수 next로 다음노드를, 변수 prev로 이전노드를 지정하여 이동할 수 있다. 또한 리스트에서 변수 head만 아니라 변수 tail도 만들어 리스트의 앞과 뒤로 접근 가능하도록 할 수 있다

예제 코드

#이중 링크드 리스트
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

##테스트
if __name__=="__main__":
    dl = DLinkedList()

삽입

1) 저장된 노드가 없는 경우(head,tail)
아무런 노드도 없는 경우는 head와 tail 값은 None이다. 때문에 head를 통해 넣든 tail을 통해 넣든 결과가 동일하다

#이중 링크드 리스트
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 #같은 노드를 가리킴

    #tail로 삽입. v : 데이터
    def insertNodeAfter(self, v):
        #없을 경우
        if self.tail is None:
            self.tail = self.Node(v)
            self.head = self.tail #같은 노드를 가리킴

##테스트
if __name__=="__main__":
    dl = DLinkedList()
    # dl.insertNodeAfter('FirstData') #head삽입 테스트
    dl.insertNodeBefore('LastData') #tail삽입 테스트

2) 저장된 노드가 있는 경우(head)
기존에 head를 차지하던 노드를 고려하면서 기존 노드의 prev를 새로 만드는 노드를 가리키도록 한다

방법

• 현재 head가 가리키는 기존 노드의 prev를 새로 생성하는 노드로 지정
• 새로 생성한 노드의 next를 기존 노드로 지정
• head를 새로 생성한 노드로 변경

#이중 링크드 리스트
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 #같은 노드를 가리킴
        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를 새로운 노드로 변경

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

3) 저장된 노드가 있는 경우(tail)

• 현재 tail가 가리키는 기존 노드의 next를 새로 생성하는 노드로 지정
• 새로 생성한 노드의 prev를 기존 노드로 지정
• tail를 새로 생성한 노드로 변경

#이중 링크드 리스트
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 #같은 노드를 가리킴
        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를 새로운 노드로 변경

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

자료 출처 [파이썬 자료구조 알고리즘 |저자: 반원]
https://wikidocs.net/book/2868