파이썬 자료구조 (4) 더블링크드리스트

더블링크드리스트

• 링크드리스트의 일방향 탐색 기능을 개선한 자료구조
• 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 가능

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self,data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def node_print(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

double_linkedlist = NodeMgmt(0)		# 0 데이터 넣기

for data in range(1, 11):			# 1~10 데이터 넣기
    double_linkedlist.insert(data)
    
double_linkedlist.node_print()

 

 

 

문제1

데이터를 앞에서부터 검색하여 해당 값이 존재하는 경우 그 값을 반환하고 존재하지 않으면 False를 반환

def search_from_head(self, data):
    if self.head == None:
        return False
    node = self.head
    while node:
        if node.data == data:
            return node.data
        else:
            node = node.next
    return False

 

 

문제2

데이터를 뒤에서부터 검색하여 해당 값이 존재하는 경우 그 값을 반환하고 존재하지 않으면 False를 반환

def search_from_tail(self, data):
    if self.tail == None:
        return False
    node = self.tail
    while node:
        if node.data == data:
            return node.data
        else:
            node = node.prev
    return False

 

 

문제3

노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 메서드 만들기

단, 기준값을 찾지 못할 경우 데이터를 삽입하지 않음

insert_before(삽입할 데이터, 기준값)
삽입할 데이터: 실제 삽입될 데이터
기준값 앞에 실제 데이터가 삽입되도록 함

 

def insert_before(self, data, after_data):
    if self.head == None:
        self.head = Node(data)
        return True
    else:
        node = self.tail
        while node.data != after_data:
            node = node.prev
            if node == None:
                return False
        new = Node(data)
        before_new = node.prev
        before_new.next = new
        new.prev = before_new
        new.next = node
        node.prev = new
        return True

 

 

 

문제1~3 전체 적용 코드 및 테스트

class Node:
    def __init__(self, data, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next
        
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self,data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def node_print(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

    def search_from_head(self, data):
        if self.head == None:
            return False
        node = self.head
        while node:
            if node.data == data:
                return node.data
            else:
                node = node.next
        return False

    def search_from_tail(self, data):
        if self.tail == None:
            return False
        node = self.tail
        while node:
            if node.data == data:
                return node.data
            else:
                node = node.prev
        return False

    def insert_before(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.tail
            while node.data != after_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.prev = before_new
            new.next = node
            node.prev = new
            return True

 

 

# 문제1 테스트

result = double_linkedlist.search_from_head(7)
print(result) # 7

result = double_linkedlist.search_from_head(17)
print(result) # False

 

 

# 문제2 테스트

result = double_linkedlist.search_from_tail(7)
print(result)	# 7

result = double_linkedlist.search_from_tail(17)
print(result)	# False

 

 

# 문제3 테스트

double_linkedlist.insert_before(6.5, 7)
double_linkedlist.node_print() # 0 1 2 3 4 5 6 6.5 7 8 9 10