Python2 09일차 수업 정리_단일 원형 연결리스트 및 각각의 장단점, 재귀함수, 스택(Stack)

- 단일 원형 연결리스트 및 각각의 장단점

- 재귀함수

- 스택(Stack)

 

---

- 단일 원형 연결리스트 및 각각의 장단점

단일 원형 연결리스트는 단순 연결리스트의 마지막 노드가 다시 첫번째 노드를

가르키도록 설정한 리스트의 형태가 원형인 구성

 

구성 환경

[데이터][다음주소값] -> [데이터][다음주소값] -> [데이터][첫번째 주소값]

 

단일원형 연결리스트 ADT 예제

특정 위치에 노드 삽입, 삭제 / 리스트가 비어있는지 확인, 크기 확인 / 전체 요소 내용 출력

class CircularLinkedList :
    # Node 클래스 선언
    class Node :
        def __init__(self, data = None, link = None) :
            self.data = data
            self.link = link
    
    # 원형연결리스트 생성자
    def __init__(self) :
        # 시작노드 초기화
        self.head = None
        # 길이(원형연결리스트 요소 개수)
        self.length = 0

    # 확인용 출력 메소드
    def show(self) :
        current = self.head

        # 반복문 사용 출력(while문의 무한루프)
        while True :
            print(current.data, end=" -> ")
            current = current.link
            # 무한 반복 종료 (조건을 걸어줌)
            if current == self.head :
                break
        print() # 줄바꿈
    
    # 연결리스트가 비어있는지 확인하는 메소드
    def is_empty(self) :
        return self.length == 0
    
    # 특정 위치에 노드를 삽입하는 메소드
    def insert(self, idx, data) :
        # idx 유효성 검사
        if idx < 0 or idx > self.length : 
            print("인덱스 범위 벗어남")
            return

        # idx 유효하다면 추가할 노드 생성
        newnode = self.Node(data)

        # 기존의 연결리스트가 비어있는지 확인
        if self.is_empty() : # 비어있다면 추가할 노드가 첫번째 노드가 되어야함
            self.head = newnode
            newnode.link = newnode # link가 None 이여선 안됨
        else : # 중간에 넣는거니까 넣는 거 전의 노드를 찾아야함
            current = self.head
            for i in range(idx-1) :
                current = current.link
            # 반복문이 다 돌면 current에는 idx전 위치의 노드의 주소값이 저장됨
            newnode.link = current.link
            current.link = newnode

            if idx == 0 : # 첫 노드에 추가
                self.head = newnode
        # 연결리스트 요소개수 +1
        self.length += 1

    # 특정 위치의 노드를 삭제하는 메소드
    def remove(self, idx) :
        # idx 유효성 검사
        if idx < 0 or idx >= self.length:
            print("인덱스 범위 벗어남")
            return
        # idx 유효, idx == 0
        if idx == 0 :
            self.head = self.head.link
            self.length -= 1
            return
        # idx != 0
        current = self.head
        for i in range(idx -1) :
            current = current.link
        # current에 삭제할 노드의 이전 노드의 주소가 저장됨
        current.link = current.link.link
                        #current.link => 삭제할 노드
        self.length -= 1

    # 연결리스트의 크기(노드의 개수)를 반환하는 메소드
    def size(self) :
        return f"현재 길이 : {self.length}"

cl = CircularLinkedList()
print(cl.is_empty()) # -> True 넣어준게 없으니까

# 데이터 삽입 확인
# insert(idx, data)
cl.insert(0, 10)
cl.show()

cl.insert(0, 20) # 20 -> 10
cl.show()

cl.insert(1, 30) # 20 -> 30 -> 10
cl.show()

cl.insert(3, 100) # 20 -> 30 -> 10 -> 100
cl.show()

# 삭제, remove(idx)
cl.remove(1)
cl.show()

# cl.remove(0)
# cl.show()

print(cl.is_empty())
print(cl.size())

 

단일 / 이중 / 원형 연결리스트의 장단점

	장점	단점
단일연결리스트	(1) 메모리를 효율적으로 사용할 수 있음 (2) 노드의 삽입, 삭제 O(1) 시간복잡도 (3) 구현이 비교적 간단하고 적은 메모리를 사용함	(1) 특정 노드를 찾으려면 처음부터 찾아야되므로 O(n) 시간복잡도 (2) 단방향으로만 이동이 가능하므로 역방향으로 이동은 어려움
이중연결리스트	(1) 양방향으로 이동이 가능하므로 노드 검색이 용이함 (2) 노드의 삽입, 삭제 O(1) 시간복잡도 (3) 양방향으로 연결이 되어 있어서  역방향 탐색이 편리함	(1) 단일연결리스트보다 메모리를 더 많이 사용함 (2) 구현이 복잡하고 코드의 양이 많아질 수 있음
원형연결리스트	(1) 특정 노드에서 시작하여 전체 노드를 순회할 때 노드의 수만큼 순회하면 원래 위치로 돌아올 수 있음 (2) 마지막 노드와 첫번째 노드가 연결되어 있어서  순회가 용이함 (3) 원형적인 구조로 알고리즘에서 활용할 수 있는  이점을 제공함	(1) 특정 노드를 탐색하려면 전체 순회해야 하여 O(n)시간 복잡도 (2) 삭제 연산이 복잡해짐

 

 

---

- 재귀함수

재귀함수란 자기 자신을 호출하는 함수

ex)

# 재귀함수 : 자신을 호출하는 함수

def recursive_print(count) :
    print(f"{count}번 함수 호출")

    if count == 3 :
        return #함수종료
    # 자기자신 호출
    recursive_print(count +1) 
    print(f"{count}번 함수 종료")

# recursive_print(0) -> recursive_print(1) -> recursive_print(2) -> recursive_print(3)
#                   <-                      <-                  <-

# 함수호출
recursive_print(0)

 

 

---

- 스택(Stack)

스택이란 데이터가 입력되면 입력되는 순서대로 쌓고 사용할 때는 나중에 들어온 것부터 먼저인 자료구조.

후입선출 == LIFO(Last In First Out)형

 

1) 활용예시 및 생활속 예시

- 글자 지우기(백스페이스 바) - 실행 취소(ctrl + z) - 웹 브라우저 방문기록(뒤로가기) - 재귀적 알고리즘(재귀함수 : 자기 자신을 호출하는 함수)

 

 

2) 스택 ADT

맨 윗부분에 요소를 추가한다 맨 윗부분에 있는 요소를 알려준다 맨 윗부분에 있는 요소를 삭제하면서 알려준다 스택이 비어있는지 확인한다 스택을 깨끗이 비운다

 

 

3) 주요함수

push()	buttom부터 차례대로 삽입된다
pop()	top부터 차례대로 삭제되며 top에 해당하는 값을 반환한다
peek()	top에 있는 요소를 알려준다
clear()	스택에 있는 모든 요소를 삭제한다

 

 

4) 필요 연산

create(size)	스택을 생성(초기화)
is_empty()	스택이 비어있다면 True, 아니라면 False
is_full()	스택이 가득차있다면 True, 아니라며 False
push(item)	만약 size를 초과한다면 함수종료, 데이터 삽입
pop()	top에 위치한 item을 반환하면서 제거
peek()	top에 위치한 item반환

top	스택 윗부분(push, pop이 이루어지는 부분)
bottom	스택 아랫부분(인덱스 0인 부분)
capacity	스택의 최대 크기(int형)

 

스택 예제)

# 리스트로 구현
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)
# 나중에 들어온 것이 먼저 나간다
stack.pop()
print(stack)
stack.pop()
print(stack)

 

 

리스트를 통한 스택구현 1

class StackWithList :
    # 생성자(스택, top의 인덱스 번호 초기화)
    def __init__(self) :
        self.stack = [] #빈리스트
        self.top_idx = None

    # 스택이 비어있는지 확인
    def is_empty(self) :
        return len(self.stack) == 0

    # 확인 출력용 메소드
    def show(self) :
        for i in self.stack[::-1] : #스택은 나중에 들어온 것부터 나간다 => 역순으로 출력
            print(i)

    # 데이터 삽입
    def push(self, data) :
        self.stack.append(data)

        if len(self.stack) == 1 :
            self.top_idx = 0 #top의 인덱스 번호 0
        else :
            self.top_idx += 1

    # 데이터 삭제
    def pop(self) :
        if self.is_empty() :
             raise IndexError("빈 스택입니다")
        data = self.stack[self.top_idx] #top의 요소를 data 변수에 저장
        del self.stack[self.top_idx]
        self.top_idx -= 1
        return data

    # top요소 확인
    def peek(self) :
        return self.stack[self.top_idx]

stack = StackWithList()

# push() : 스택에 데이터 추가
stack.push(1)
stack.push(2)
stack.push(3)
print("=====")
stack.show()

# pop() : 스택의 데이터 삭제
print('=====')
print(f"삭제 데이터 : {stack.pop()}")
stack.show()

# peek() : top요소 확인
print(f"top 데이터 : {stack.peek()}")

 

 

2024.02.21