[n521] Data Structure

자료구조

• 선형 자료구조 : 데이터들을 일렬로 나열된 형태로 저장할 때 사용
  • (정적)배열, 동적 배열, 연결 리스트
  • 배열 : 반드시 선언할 때 크기를 결정 => 크기는 고정적, 절대 변경 불가. 메모리 상에서 배열의 원소들이 연속적으로 붙어 있다. 
    • 장점 : 인덱스를 통해서 빠르게 접근 가능 (Read가 쉽다)
    • 단점 : 크기가 고정적이므로 그 크기보다 많은 데이터가 들어오면 혼란스럽다. 
    • 데이터 추가 : O(n)
  • 동적 배열 : 배열의 크기를 유동적으로 조절할 수 있는 배열. 메모리 상에서 배열의 원소들이 연속적으로 붙어 있다.
    • 장점 : 인덱스를 통해서 빠르게 접근 가능 (Read가 쉽다). 배열의 크기 유동적으로 조절 가능
  • 연결 리스트 : 원소들이 메모리 상에서 연속적으로 붙어 있지 않다. => 인덱스로 빠른 접근 불가. 
    • 장점 : 삽입, 삭제의 연산이 간편하다 => O(1)이 가능. 동적으로 배열 크기 사용 가능. 
    • 단점 : 랜덤 액세스(메모리의 주소로 어느 부분에서도 데이터를 읽는 방식)가 불가능 하다.  
    • Random Access <-> Sequential Access
    • 데이터 탐색 : O(n)

연결리스트(Linked List)와 배열(Array), 그리고 시간복잡도의 차이에 대해

• 비선형 자료구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태
  • 트리, 그래프

 

 

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

• 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  # 다음노드를 현재노드에 저장하면서 위치를 바꾼다.

# 클래스에 연결리스트 구현
class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

class linked_list:
  def __init__(self, value):
    self.head = Node(value)

  def add_node(self, value):
    if self.head == None:
      self.head = Node(value)
    else:
      node = self.head
      while node.next:
        node = node.next
      node.next = Node(value) # init함수의 value

  # 연결리스트의 삭제구현
  def del_node(self,value):
    if self.head == None:
      # 해당 값에 대한 노드는 없다.
      # 의미없는 조건에서 함수는 아무것도 반환하지 않는다. 
      print('해당 값에 대한 노드가 없습니다')
      return
    elif self.head.value == value:
      # 노드의 위치를 변경시킨다.
      # 변경된 노드에 대해서 삭제를 진행한다.
      temp = self.head
      self.head = self.head.next
      del temp
    else:
      node = self.head
      while node.next:
        if node.next.value == value:
          temp = node.next
          node.next = node.next.next
          del temp
          return
        else : 
          node = node.next

  # 연결리스트의 노드출력을 위한 기능
  def ord_desc(self):
    node = self.head
    while node:
      print(node.value)
      node = node.next

[자료구조] 연결 리스트 (Linked List)

 

 

큐 (Queue)

• 큐는 FIFO(선입 선출) 즉, 먼저 들어간 데이터가 먼저 나오는 구조이다.
• 예를 들어 줄을 길게 선 사람들을 생각할 수 있다. 먼저 선 사람이 먼저 들어간다. 
• deque (덱) : double-ended queue의 줄임말
  • 큐와 스택의 장점을 합쳐둔 구조이다. 
  • double은 자료구조에서 양방향을 의미한다.

[자료구조] 큐 (Queue)

 

 

스택 (Stack)

[자료구조] 스택 (Stack)

# 리스트 메소드를 사용해서 스택만들어보기

stack = [3, 4, 5]
stack.append(6)
stack.append(7)
print(stack)

stack.pop()
print(stack)

stack.pop()
print(stack)

stack.pop()
print(stack)

# 위의 코드처럼 push와 pop을 활용해서 공간에 값이 유동적으로 변한다.(동적처리)

# [연결리스트를 이용한 스택 구현]
# 아래의 코드는 스택이 내부적으로 어떻게 작동되는지 확인하기 위해 작성되었다.
# 파이썬에서 자체적으로 제공하는 리스트의 append, pop 메소드를 활용하면 쉽게 구현될 수 있지만,
# 아래처럼 다른 방법으로도 구현하는 코드를 보면서 스택에 대한 이해도를 높일 수 있다.

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        # 신규 노드 생성
        new_node = LinkedListNode(data)
        # 최상단의 노드를 신규 노드 다음 노드로 삽입
        new_node.next = self.top
        # 신규 노드를 최상단에 삽입
        self.top = new_node
        return new_node.data

    def pop(self):
        # 스택이 비어있는지 확인
        if self.top is not None:
            # 최상단의 노드를 삭제할 노드로 삽입
            popped_node = self.top
            # 삭제할 노드 다음 노드를 최상단의 노드로 삽입
            self.top = popped_node.next
            # 삭제할 노드로부터 값 리턴
            return popped_node.data

    # 연결리스트의 노드출력을 위한 기능
    def ord_desc(self):
        node = self.top
        while node:
            print(node.data)
            node = node.next