4. 파이썬의 더블 링크드 리스트

1. 더블 링크드 리스트
- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능


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 sesrch_from_head(self, data):
      pass

  def sesrch_from_tail(self, data):
      pass


double_linkedlist.node_print()

--> 
0
1

 

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

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

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 sesrch_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 sesrch_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(삽입할 데이터, 기준값)
삽입할 데이터 : 실제 삽입될 데이터
기준값 : 기준값 앞에 데이터가 삽입되도록 함

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


double_linkedlist = NodeMgmt(0)

for data in range(1, 11):
    double_linkedlist.insert(data)

double_linkedlist.node_print()
-->
0
1
2
3
4
5
6
7
8
9
10