지난 번에 단순 연결리스트를 구현해보았고 이번에는 이 단순 연결리스트를 이용하여 먼저 들어온 친구는 가장 나중에 나가는 Stack이라는 자료구조를 만들어보려고 합니다.
파이썬에서는 이미 스택 자료구조를 리스트 자료형(동적배열)을 이용하여 구현이 되어있습니다.
파이썬으로 연결리스트 만들기 4탄 : 단순 연결리스트 삭제연산 (맨 앞 노드 삭제 / 맨 뒤 노드 삭
이번에는 단순 연결리스트에서 노드를 삭제하는 방법을 알아보겠습니다. 노드를 삭제할 때는 맨 앞 노드를 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제로 경우를 나눌 수 있습니다. 그렇다면 삭제
c-i-s.tistory.com
우선 지난번에 만든 단순 연결리스트의 시간복잡도를 알아보겠습니다. (추가, 삽입, 삭제, 탐색)
| 추가연산 | O(1) | |
| 삽입연산 | O(1) -> 맨 앞, 뒤 | O(n) |
| 삭제연산 | O(1) -> 맨 앞, 뒤 | O(n) |
| 탐색연산 | O(1) -> 맨 앞, 뒤 | O(n) |
추가연산의 경우 무조건 tail노드 뒤에만 추가하니까 바로바로 추가할 수 있습니다. 때문에 시간복잡도는 O(1)입니다.
삽입연산의 경우에 맨 앞에 삽입할 경우와 맨 뒤에 삽입은 바로바로 넣을 수 있어서 O(1)이지만 맨 뒤에서 두 번째에 넣을 경우에는 O(n-1)이지만 -1은 무시해서 O(n)이라고 할 수 있습니다. 이는 삭제 연산도 마찬가지 입니다.
탐색연산의 경우 양 끝을 탐색하는 경우 바로 찾을 수 있어서 O(1)이라 할 수 있고 맨 뒤에서 두 번째를 탐색할 경우 O(n-1)이지만 -1은 무시해서 O(n)이라 할 수 있습니다.
사실 추가 연산을 빼고 삽입, 삭제, 탐색에서 O(1)이 나올 경우는 극히 드물다고 봐도 무방합니다. 따라서 그냥 O(n)으로 쳐도 됩니다.
연결리스트로 스택을 만들지 않는 이유는 동적배열은 탐색하는데 걸리는 시간이 O(1)이지만 연결리스트는 O(n)의 시간이 걸리기 때문입니다. 그렇지만 그냥 연습을 위해서 만들어보도록 하겠습니다.
우선 스택의 기능을 알아보겠습니다.
1. push
2. pop
3. 비었나?
4. 스택의 길이
5. 스택 맨 위의 값
이렇게 다섯 가지가 있다고는 하는데 사실 1번 2번 빼고는 다 편의 기능들이라 구현에 큰 의미는 없습니다.
스택은 가장 먼저 들어온 값이 가장 나중에 나가게 됩니다. 이를 그림으로 알아보면 다음과 같습니다.
data1이 가장 먼저 들어왔고 data3이 가장 나중에 들어왔습니다. 스택 자료구조는 위가 뻥 뚫려있어서 가장 나중에 들어온 것이 가장 먼저 나갈 수 있습니다. 이를 First in Last out 줄여서 FILO 구조라고 합니다.
단순 연결리스트를 이용하여 스택을 구현할 것입니다.
기존에 있던 것 코드 중에 __str__만 빼주겠습니다.
class Node:
def __init__(self, data):
self.data = data # 노드의 값
self.next = None # 다음 노드를 가리키는 정보
class LinkedList():
def __init__(self):
# 연결리스트를 처음 생성 시 아무것도 없으므로 다음과 같이 초기화 할 수 있다.
self.head = None
self.tail = None
self.count = 0
def append(self, value):
"""연결리스트 뒤에 추가하는 메소드"""
new_node = Node(value) # 공통 특징은 우선 새 노드를 생성한다는 것
if self.count == 0: # 연결리스트가 비었을 때
self.head = new_node # 새 노드가 head node가 된다.
self.tail = new_node # 새 노드가 tail node가 된다.
else: # 연결리스트가 안 비어있을 때
self.tail.next = new_node # tail node의 다음이 새 노드를 가리킨다
self.tail = new_node # 새 노드는 tail node가 된다
self.count += 1 # 노드가 추가 되었으니까 갯수를 하나 올린다.
def insert(self, index, value):
"""연결리스트의 원하는 위치에 삽입하는 메소드"""
new_node = Node(value)
if 0 <= index <= self.count: # 연결리스트의 원하는 인덱스 범위에 있나?
if index == 0: # 인덱스가 0이란 맨 앞에 넣고 싶다는 뜻
head_node = self.head # head를 잠시 저장
self.head = new_node # head 노드를 새 노드로 교체
self.head.next = head_node # head(신)의 다음을 아까 잠깐 저장한 head(구)를 가리킴
elif index == self.count: # 이 말은 만약 tail 노드라면?
self.tail.next = new_node # tail의 다음을 새 노드를 가리킴
self.tail = new_node # tail을 새 노드로 교체
else: # 나머지 경우는 일반적인 중간에 넣는 것임
i = self.head
for _ in range(index - 1):
i = i.next
prev_node = i # 삽입할 위치의 이전 노드
new_node.next = prev_node.next # 새 노드의 다음은 이전 노드의 다음을 연결해준다.
prev_node.next = new_node # 이전 노드의 다음은 새 노드를 연결한다.
self.count += 1 # 노드를 삽입했으니까 1 올림
else: # 범위에 없으면 인덱스를 잘못 입력했다고 출력해줄까?
print("인덱스를 잘못 입력했습니다.")
def remove(self, index):
"""연결리스트의 원하는 노드를 지운다."""
if index == 0: # 맨 앞을 의미한다.
self.head = self.head.next
elif index == self.count-1: # count에서 1을 빼면 맨 뒤를 의미함
i = self.head # head 부터 시작해서
for _ in range(self.count-2): # -2를 해야 딱 그 전까지 찾기 가능
i = i.next
tail_prev_node = i
self.tail = tail_prev_node
self.tail.next = None # 다음이 없어야 하므로 None 값을 넣어줍니다.
elif 0 < index < self.count-1: # 중간 노드를 지울 경우
i = self.head
for _ in range(index-1): # 이전을 찾기 위해서 반복은 index-1번만 합니다.
i = i.next
remove_prev_node = i # 지우는 노드 이전
remove_node = remove_prev_node.next # 지우는 노드
temp = remove_node.next # 지울 노드의 다음 노드로 갈 정보
remove_prev_node.next = temp # 그 정보를 지울 노드의 이전의 다음으로 갈 정보로 준다
self.count -= 1 # 지웠으니까 노드의 개수도 하나 줄어듬이 코드 바로 밑에 Stack을 만들어보겠습니다.
연결리스트를 상속시켜서 만들어보겠습니다. 상속은 말 그대로 물려받는다는 의미인데 복잡하게 상속을 알아보지 말고 간단하게만 알아보겠습니다.
상속은 부모로부터 물려받는 것입니다. 즉, 클래스를 물려받습니다. 물려받으면 자신의 클래스 안에서 사용할 수 있습니다. 물론 상속을 받지 않아도 사용할 수 있지만 그것은 public한 클래스일 경우입니다. 상속은 복잡하게 들어가면 너무 복잡합니다. 간단한 상속을 다룰 예정입니다.
class Stack(LinkedList):
def __init__(self):
super().__init__()class Stack(LinkedList):
=> Stack 클래스는 LinkedList 클래스를 상속받는다는 의미입니다.
super().__init__()
=> 상속받은 LinkedList 클래스의 인스턴스 변수를 초기화합니다.
=> 참고로 super()를 사용하여 부모 클래스의 메소드를 불러올 수 있습니다.(예시 : super().append())
이제 push 메소드 구현입니다.
class Stack(LinkedList):
def __init__(self):
super().__init__()
def push(self, value):
"""스택에 value 넣기"""
super().append(value)
# LinkedList.append(self, value) # 바로 위에 문장과 같은 역할을 한다.정말 단순한 형태입니다. super().append()를 이용하여 부모 클래스의 메소드를 호출합니다. push의 기능은 그냥 추가하는 것 밖에 없기 때문에 연결리스트에 추가하는 메소드를 활용합니다.
pop의 구현입니다.
pop은 가장 나중에 넣은 것을 꺼내오는 것입니다. 단순히 지우는 것이 아니라 데이터를 꺼내고 지우는 과정이 들어갑니다.
class Stack(LinkedList):
def __init__(self):
super().__init__()
def push(self, value):
"""스택에 value 넣기"""
super().append(value)
# LinkedList.append(self, value) # 바로 위에 문장과 같은 역할을 한다.
def pop(self):
temp = self.tail.data
super().remove(self.count-1)
return temptemp = self.tail.data
=> 가장 마지막의 값을 잠시 저장합니다.
super().remove(self.count-1)
=> 부모 클래스의 remove 메소드를 사용합니다.
이렇게 가장 중요한 push와 pop 기능이 완성되었습니다. 나머지 3개의 기능은 편의기능이라서 그냥 코드만 첨부하겠습니다.
class Stack(LinkedList):
def __init__(self):
super().__init__()
def push(self, value):
"""스택에 value 넣기"""
super().append(value)
# LinkedList.append(self, value) # 바로 위에 문장과 같은 역할을 한다.
def pop(self):
"""스택의 값을 빼내온다."""
temp = self.tail.data
super().remove(self.count-1)
return temp
def isempty(self):
"""스택이 비어있는지 True False로 표현"""
if self.count == 0:
return True
else:
return False
def stack_len(self):
"""스택에 몇 개의 데이터가 있는지 반환한다."""
return self.count
def top(self):
"""맨 위에 어떤 값이 있는지 값만 반환한다."""
if self.count == 0:
return "값이 없습니다."
else:
return self.tail.data
def __str__(self):
"""자동으로 출력해주는 메소드 사용법은 인스턴스를 출력시키면됩니다."""
i = self.head
result = ""
while True:
if i.next is None:
result += str(i.data)
break
else:
result += str(i.data) + " -> "
i = i.next
return result'프로그래밍 > 자료구조' 카테고리의 다른 글
| 파이썬으로 이중연결리스트를 만들어보자! (추가 연산, 탐색 연산) (0) | 2023.01.29 |
|---|---|
| 파이썬으로 연결리스트 만들기 4탄 : 단순 연결리스트 삭제연산 (맨 앞 노드 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제 방법) (0) | 2023.01.01 |
| 파이썬으로 연결리스트 만들기 3탄 : 단순 연결리스트 삽입 연산(원하는 곳에 삽입하자! / 맨 뒤에 삽입 / 맨 앞에 삽입 / 중간에 삽입) (0) | 2022.12.06 |
| 파이썬으로 연결리스트 만들기 2탄 : 단순 연결리스트 추가 연산 (연결리스트 자동 출력 만들기) (0) | 2022.12.04 |
| 파이썬으로 연결리스트 만들기 1탄(자료구조 / 단순 연결리스트 / 이중 연결리스트 / 추가 / 삽입 / 삭제 / 접근) (0) | 2022.12.04 |
댓글