[자료구조] 스택 및 링크드리스트

[자료구조]

자료구조 강의

스택

스택

데이터를 한쪽 끝에서만 자료를 넣고 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼내는(LIFO) 데이터 구조

• 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

• 스택의 장점 구조가 단순하여 구현이 쉽다. 데이터 저장/읽기 속도가 빠르다.

• 스택의 단점 데이터 최대 개수를 미리 정해야 한다. 저장 공간의 낭비가 발생할 수 있다.

• 스택 - 재귀함수

# 재귀 함수
def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)
recursive(4)

실핼 결과: 4 3 2 1 0 ended returned 0 returned 1 returned 2 returned 3 returned 4

링크드 리스트

• 링크드 리스트의 구조
  - 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
  - 노드 : 데이터 저장 단위(데이터 값, 포인터)로 구성 / 데이터와 주소를 가지는 것
  - 포인터 : 각 노드 안에서 다음 노드와의 연결 정보를 가지고 있는 공간(참조 값을 가지고 있음)

• 노드의 장점

  미리 데이터 공간을 할당하지 않아도 된다.

• 노드의 단점

  연결을 위한 데이터 공간이 필요하므로 저장공간 효율이 좋지는 않음
  접근 속도 느림
  중간 데이터 삭제 시 앞뒤 데이터 재구성 필요

• 노드 구현 (파이썬)

1. Node를 찍어낼 class 생성

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

2. Node 생성 및 Node 연결

   node1 = Node(1)
   node2 = Node(2)
   node1.next = node2 # node2가 저장되어 있는 주소를 node1의 next에 넣는다.
   head = node1 # 가장 맨 처음 Node는 알고 있어야 하기 때문에 head를 node1의 주로소 놓는다.
   

3. Node 관련 메서드 정의 (add, desc/print, delete)

   class NodeMgmt:
       def __init__(self, data):
           self.head = Node(data)
   
       def add(self, data):
           if self.head == '':
               self.head = Node(data)
           else:
               node = self.head
               while node.next:
                   node = node.next
               node.next = Node(data)
   
       def desc(self):
           node = self.head
           while node:
               print (node.data)
               node = node.next
   
       def delete(self, data):
           if self.head == '':
               print ("해당 값을 가진 노드가 없습니다.")
               return
   
           # head 부분 삭제
           if self.head.data == data:
               temp = self.head
               self.head = self.head.next # head의 다음 node를 head로 설정
               del temp # head(였던) 주소 삭제
           else: # 중간 노드 및 tail 삭제
               node = self.head
               while node.next:
                   if node.next.data == data:
                       temp = node.next
                       node.next = node.next.next # node 다다음 노드를 다음 노드로 하겠다는 것 / 다음 노드를 삭제하겠다는 것
                       del temp
                       return
                   else:
                       node = node.next # 다음 노드 다음 노드 이동