단순 연결 리스트

---

단순 연결 리스트

• 동적 메모리 할당을 이용해 노드들을 한 방향으로 연결하여 구현
• 삽입이나 삭제 시 항목들의 이동이 필요 없음
• 항목을 탐색하려면 순차 탐색을 해야함
  

단순 연결 리스트 삽입

단순 연결 리스트 삭제

class SList:                        # 연결리스트 클래스
  class Node:                       # 노드 클래스
    def __init__(self, item, link):  # 노드 생성자 
        self.item = item
        self.next = link

  def __init__(self):  # 단순 연결 리스트 생성자   
    self.head = None
    self.size = 0

def insert_front(self, item):  # 연결 리스트의 맨 앞에 새 노드 삽입
  if self.size == 0:
    self.head = self.Node(item, None)       # 기존에 노드 존재 X  # 연결리스트 빈 상태 
  else:     
    self.head = self.Node(item, self.head)  # 기존에 노드가 존재 할경우 # 연결리시트 비어있지 X
    self.size += 1

    def delete_front(self):  # 연결 리스트의 맨 앞 노드 삭제
        if self.size == 0:      # 연결리스트 빈 상태 
            print('리스트 empty')
        else:                   # 연결리시트 비어있지 X
            self.head = self.head.next
            self.size -= 1

    def search(self, target):  # item 이 target 인 노드 탐색
        p = self.head
        for k in range(self.size):
            if target == p.item:
                return k
            p = p.next
        return None

    def print_list(self):  # 연결 리스트 출력
        p = self.head
        while p:
            print(p.item, ' -> ', end=' ')
            p = p.next
        print()

---

스택 자료구조

• 한쪽 끝에서 항목을 삭제(pop)하거나 새로운 항목을 저장(push)
• 한쪽 끝을 나타내는 top 변수
• 후입선출 (Last-In First-Out,LIFO)
• 선형 자료구조 : 리스트나 단순연결 리스트로 구현
  

1. 리스트로 구현한 스택

def push(item):  		# 삽입 연산
    stack.append(item)


def pop():  			# 삭제 연산
    if len(stack) != 0:   
        item = stack.pop(-1)
        return item

top = len(stack) 		# top 크기

2. 사용자 정의 stack class

# 리스트로 stack 구현
class MyStack:
  # 스택 생성자 정의
  def __init__(self):
    self.stack_list = [] # list stack
  # 스택 클래스 메소드
    # 스택 상태 확인
  def is_empty(self):
    if len(self.stack_list) == 0:
      return True
    return False
  # 스택 삽입 메서드
  def push(self, value):
    self.stack_list.append(value)
  # 스택 삭제 메서드
  def pop(self):
    if len(self.stack_list) != 0:
      return self.stack_list.pop()

---

큐 자료구조

• 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조이다
• 뒤(rear)에서 새 항목 삽입 연산: rear 변수
  - rear 큐의 가장 오른쪽(뒤)에 있는 항목을 참조하는 레퍼런스
• 앞(front)에서 삭제 연산: front 변수
  - front 큐의 가장 왼쪽(앞)에 있는 항목을 참조하는 레퍼런스
• 선입 선출(First-In Last-Out,FIFO)
• 선형 자료구조: 리스트나 단순 연결 리스트로 구현
  

1. 리스트로 구현한 큐

def add(item):  # 삽입 연산
    q.append(item) # 뒤 (rear) 추가 


def remove():   # 삭제 연산
    if len(q) != 0:  # pop(0) 을 통해 맨 앞(front) 제거
        item = q.pop(0)
        return item

2. 사용자 정의 queue 클래스 : 리스트로 구현

# 리스트로 queue 구현
class Queue:
  def __init__(self):
    self.data = []

  def is_empty(self):
    if len(self.data) == 0:
      return True
    return False

  def enqueue(self, value):
    self.data.append(value)

  def dequeue(self):
    self.data.pop(0)

  def peek(self):          # 맨 앞(front) 데이터 확인  
    if not self.is_empty():
      return self.data[0]
    return