3. 파이썬의 링크드 리스트

1. 링크드 리스트(Linked list)

- 떨어진 곳에 존재하는 데이터를 화살표로 연결하여 관리하는 구조
- C언어에서느  중요한 자료구조이지만, 파이썬에는 리스트 타입이 링크드리스트 역할도 이미 지원함
-데이터의 삽입과 삭제가 매우 빠름

2. 링크드 리스트 용어
- 노드(Node) : 데이터 저장 단위(데이터, 포인터)로 구성
- 포인터(Pointer ) : 각 노드안에서 다음이나 이전의 노드와의 연결정보를 가지고 있는 공간


#링크드 리스트 구현
파이썬에서는 링크드 리스트를 구현할때 클래스를 주로 활용

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


# Node 객체와 Node 객체의 연결하기(포인터 활용)
node1 = Node(1)
node2 = Node(2)
print(node1)
print(node2)
-->
<__main__.Node object at 0x782ce942c820>
<__main__.Node object at 0x782ce942c3a0>



node1.next = node2
head = node1

#링크드 리스트로 데이터 추가하기
class Node:
  def __init__(self,data):
    self.data = data
    self.next = None
  def add(self, data):
    node = head
    while node.next:
      node = node.next
    node.next = Node(data)


node1 = Node(1)
head = node1
for index in range(2, 11):
    node1.add(index)
    

#링크드 리스트 데이터 출력하기
node = head
while node.next:
  print(node.data)
  node = node.next
print(node.data)

-->
1
2
3
4
5
6
7
8
9
10


## 문제 1
* 3.5 현재 링크드리스트 객체에 3.5 데이터를 삽입하려고함
* (단, 3.5는 3과4 사이에 넣을 수 있도록 함)
데이터를 삽입
node2 = Node(3.5)
node = head
search = False
while not search:
  if node.data == 3:
    search = True
  else:
    node = node.next

node_next = node.next # 3번 노드의 포인터에 저장된 4번주소를 node_next에 넣어줌
node.next = node2 #3번 노드의 포인터에 3.5 의 주소를 넣어줌
node2.next = node_next #3.5의 노드의 포인터에 4의 주소를 넣어줌

node = head
while node.next:
  print(node.data)
  node = node.next
print(node.data)
-->
1
2
3
3.5
4
5
6
7
8
9
10


문제 2
링크드 리스트를 객체지향 프로그래밍으로 구현하기

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


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

  def add(self, data): #  노드를 추가
      if self.head == None:
        self.head = None(data)
      else:
          node = self.head
          while node.next:
            node = node.next
          node.next = Node(data)

  def node_print(self): #모든 노드를 출력
    node = self.head
    while node:
      print(node,data)
      node = node.next

  def delete(self, data):
    #head에 노드가 없을 경우
    if self.head == None:
      print('head에 노드가 없습니다.')
      return

    #지우려는 값이 헤드에 있는경우
    if self.head.data == data:
      print('지우려는 값이 head에 있습니다.')
      temp = self.head
      self.head = self.head.next
      del temp
      #지우려는 값이 head에 없는경우
    else:
      print('지우려는 값이 head에 없습니다.')
      node = self.head
      while node.next:
        if node.next.data == data:
          temp = node.next
          node.next = node.next.next
          del temp
          return
        else:
          node = node.next

linkedlist = NodeMgmt(0)
linkedlist.delete(4)
-->
지우려는 값이 head에 없습니다.