#4. 이중연결리스트 (Double Linked List) / python으로 구현

2023.10.05 - #3. 연결리스트 (Linked list) / python으로 구현

#3. 연결리스트 (Linked list) / python으로 구현

지난번엔 연결리스트에 대해서 알아보고 단일 연결 리스트를 구현해보았습니다.

단일연결 리스트란 Node가 다음 노드를 가리키는 next만 가지고 있는것입니다. 

오늘 구현해볼 이중연결리스트 (double linked list)는 이전 노드를 값이 추가된 노드입니다. 

출처: geeksforgeeks

단일 연결리스트는 next만 가지고 있어서 전방탐색만 가능하고 , 이중연결리스트는 앞, 뒤 모두 탐색 가능합니다. 대신 메모리를 더 사용하기 때문에 사용목적에 따라 구현하는것이 좋습니다. 

 

코드 구현하기

• 자료구조: 이중연결리스트
• 기능
  • 홈페이지 방문 및 뒤로가기, 앞으로가기 기능
  • visit(self, url): url 노드 추가 후 current 노드로 지정, 만약 뒤로가기 후 visit 실행한다면 앞서 있는 노드는 버리고 새로운 visit 노드로 연결 시작 
  • back(self, steps): steps 만큼 뒤로 가고 만약 step보다 노드의 길이가 짧다면 가장 첫번째 노드 반환
  • forward(self, steps): steps 만큼 앞으로 가고 만약 step보다 남은 노드 길이가 짧다면 마지막 노드 반환
• 코드
  • visit 코드 순서 구상
    
    • url 노드 생성
    • cur 노드의 Next를 새로 생성한 노드에 연결
    • 새로 생성한 노드의 prev를 cur 노드로 연결
    • cur 을 새로 생성한 노드로 연결 
  • back 코드 순서 구상
    • steps 만큼 cur = cur.prev 로 뒤로가기 해줌
    • for문 도는동안 만약 step이 남았는데 cur.prev가 없다면 (현재 노드가 마지막) 현재 값을 return 
  • forward 코드 순서 구상
    • steps 만큼 cur = cur.next 로 앞으로가기 해줌
    • for문 도는동안 만약 step이 남았는데 cur.next가 없다면 (현재 노드가 마지막) 현재 값을 return 

class ListNode(object):
    def __init__(self, val, next = None, prev = None):
        self.value = val
        self.next = next
        self.prev = prev

class Homepage(object):
    def __init__(self, homepage):
        self.head = self.cur = ListNode(val = homepage)
    def visit(self, url):
        self.cur.next = new_node = ListNode(val = url, prev = self.cur)
        self.cur = self.cur.next
        return None

    def back(self,steps):
        for s in range(steps):
            if self.cur.prev == None:
                return self.cur.value
            self.cur = self.cur.prev
        return self.cur.value

    def forward(self,steps):
        for s in range(steps):
            if self.cur.next == None:
                return self.cur.value
            self.cur = self.cur.next
        return self.cur.value

h = Homepage('naver')
h.visit('kakao')
h.visit('google')
h.visit('daum')
print(h.back(2))
h.visit('github')
print(h.forward(2))

- 테스트 결과

- naver -> kakao-> google -> daum -> (back 2 step ) -> kakao -> github -> (forward 2 step) -> github 

 

 

*참고

- https://www.geeksforgeeks.org/data-structures/linked-list/doubly-linked-list/