ADT(추상자료형)의 구체적 시작

데이터를 관리하기위한 추상자료형과 자료구조 도구들

자료구조 핵심 : ADT(Abstract Data Type)

💡 생각하는 시간 : ADT를 활용하는 이유?

• 프로그래밍엔 데이터 처리를 위한 자료형이 존재
• 파이썬에서 기본 자료형: 프로그램밍을 위한 도구들, 숫자, 문자열, 리스트, 딕셔너리 등
• ADT는 추상적으로 필요한 기능을 나열한 일종의 명세서**(로직)**
  • ADT는 기본자료형(대표적으로 리스트, 숫자, 문자열)을 활용하여 사용자에 의해 구현
• 추상화는 소프트웨어가 발전하면서 프로그램의 크기나 복잡도가 같이 증가하였고 프로그램의 핵심 부분을 간단하게 설명하기 위한 것
  • 참고내용 : 추상화(요약)

linked-list(연결리스트)

🔍 자세히보기 : 리스트와 연결리스트

• 연결리스트는 말 그대로 리스트들을 '연결'
  • 연결은 프로그래밍에서 참조의 기능으로 구현 → 연결리스트는 리스트의 길이를 별도로 지정해줄 필요없음
  • 위에서 보는 것처럼 연결리스트는 별도의 인덱스를 지정할 필요없이 연결되는 구조

• 배열은 요소를 직접 접근하여 저장하고 인덱스를 활용
• 연결리스트의 각 요소는 참조하는 노드에 저장
  • 각 노드는 연결리스트의 다음 노드에 대해 **참조(또는 '포인터')**를 함
    • 참조기호 : .
    • 삽입, 할당기호 : =

# 연결리스트의 노드를 저장하는 첫 단계

class Node:
  def __init__(self,value,next=None):
    self.value = value  # 노드의 값을 나타내는 value
    self.next = next  # 노드의 다음위치를 가리키는 next의 초기값은 None

class linked_list:
  def __init__(self,value):
    self.head = Node(value) # 초기 클래스에 head노드선언

  def add_node(value):
    print('head.value:', head.value)
    print('head.next:', head.next)
    node = head           # 첫번째 위치에 해당하는 head를 생성하고, node 변수에 저장
    while node.next:      # head노드의 다음위치에 노드가 생성될 때까지 반복문 진행
      node = node.next    # head노드의 다음위치에 노드가 있는 경우(두번째 노드라고 가정),
      print('print in while:', node.next)
                          # 두번째 노드부터 node변수에 저장
    node.next = Node(value) # 데이터를 노드 다음위치에 저장

# 연결리스트의 노드값들에 대해

head = Node(5)    # head노드에 값5를 저장
linked_list.add_node(11) # 값11을 추가

print(head.value) # head노드의 값은 5
print(head.next.value) # head노드의 다음위치노드의 값은 11

• 연결리스트의 핵심 개념은 연결이고, 이것은 참조되는 노드의 '위치바꾸기'

# 리스트를 연결
node1 = Node(3)
node2 = Node(4)

node3 = Node(5)
node4 = Node(6)

node1.next = node2
node2.next = node3
node3.next = node4

node = node1        # 첫번째노드부터 시작
while node:         # 노드별로 반복문을 수행
  print(node.value)
  node = node.next  # 다음노드를 현재노드에 저장하면서 위치를 바꿈