2026.11.17 · 7분 읽기 · 조회 0
연결된 구조는 흩어진 데이터를 링크로 연결해서 관리한다.


용량이 고정되지 않는다.

중간에 자료를 삽입하거나 삭제하는 것이 용이하다.
-> 시간 복잡도: O(1)
n번째 항목에 접근은 시간이 오래 걸린다.
-> 시간 복잡도: O(n)





class Node: # 단순 연결리스트를 위한 노드 클래스
def __init__(self, elem, link=None): # 생성자. 디폴트 인수 사용
self.data = elem # 데이터 멤버 생성 및 초기화
self.link = link # 링크 생성 및 초기화class LinkedStack:
def __init__(self): # 생성자
self.top = None # top 생성 및 초기화
def isEmpty(self): return self.top == None # 공백상태 검사
def clear(self): self.top = None # 스택 초기화def push(self, item):
n = Node(item, self.top) # 노드의 다음 링크로 self.top을 줌
self.top = n
def pop(self):
if not self.isEmpty(): # 공백이 아니면
n = self.top # 현재 top 노드의
self.top = n.link # 다음 노드를 top으로 지정
return n.data # 이전의 top 데이터 반환
def size(self):
node = self.top # top에서 시작
count = 0
while not node == None: # 노드가 None이 될 때 까지
node = node.link # 다음 노드로 이동
count += 1 # count 증가
return countdef peek(self):
if not self.isEmpty():
return self.top.data
def display(self, msg=`LinkedStack : `):
print(msg, end="")
node = self.top # top에서 시작
while not node == None: # 노드가 없을 때 까지
print(node.data, end=' ') # 노드 출력
node = node.link # 다음 노드로 이동
print()class LinkedList:
def __init__(self):
self.head = None
def isEmpty(self): return self.head == None # 공백상태 검사
def clear(self): self.head = None # 리스트 초기화
def size(self):
node = self.head # head에서 시작
count = 0
while not node == None: # 노드가 None이 될 때 까지
node = node.link # 다음 노드로 이동
count += 1 # count 증가
return count
def display(self, msg=`LinkedStack : `):
print(msg, end="")
node = self.head # head에서 시작
while not node == Node: # 노드가 없을 때 까지
print(node.data, end=' ') # 노드 출력
node = node.link # 다음 노드로 이동
print()def getNode(self, pos):
if pos < 0: return None # 음수면 None 리턴
node = self.head # head부터 시작
while pos > 0 and node != None: # pos 번 반복
node = node.link # 다음 노드로 이동
pos -= 1
return node # 최종 노드 반환def getEntry(self, pos):
node = self.getNode(pos)
if node == None: return None
else: return node.datadef replace(self, pos, ele):
if pos < 0: pos = 0
if pos >= self.size(): pos = self.size() - 1
node = self.getNode(pos)
node.data = eledef find(self, data):
node = self.head # head부터 시작
while node is not None:
if node.data == data: return node # 데이터가 같으면 노드 반환
node = node.link # 다음 노드로 이동
return node # 다 돌면 None 반환4가지 경우를 고려해야 한다.
def insert(self, pos, elem):
before = self.getNode(pos-1) # 삽입 위치 바로 앞 노드 찾기
if before == None: # 앞 노드가 없으면
self.head = Node(elem, self.head) # 맨 앞에 삽입
else:
node = Node(elem, before.link) # before의 다음 노드를 가리키게 함
before.link = node # before가 새 노드를 가리키게 함
4가지 고려 사항이 있다.
def delete(self, pos):
before = self.getNode(pos-1) # 이전 노드 찾기
if before == None: # 이전 노드가 없음 -> 맨 앞 노드 삭제
if self.head is not None: # 리스트가 비어 있지 않으면
self.head = self.head.link # head를 다음 노드로 연결
elif before.link != None: # 삭제할 노드가 실제로 존재하면
before.link = before.link.link # 삭제할 노드를 건너뛰고 연결


class CircularLinkedQueue:
def __init__(self):
self.tail = None # tail: 유일한 데이터
def isEmpty(self): return self.tail == None
def clear(self): self.tail = None # 큐 초기화
def peek(self):
if not self.isEmpty():
return self.tail.link.data # front의 데이터 반환def enqueue(self, item):
node = Node(item, None) # 노드 생성
if self.isEmpty(): # 큐가 공백일 때
node.link = node # 자기자신을 링크
self.tail = node
else: # 큐가 공백이 아니면
node.link = self.tail.link # 노드의 링크를 front에 연결
self.tail.link = node # 이전의 tail 다음 노드를 새 노드로 변경
self.tail = node # 새 노드를 tail로 변경

def dequeue(self):
if not self.isEmpty(): # 큐가 공백이 아닐 때
data = self.tail.link.data # data = front의 데이터
if self.tail.link == self.tail: # front == tail일 때(노드가 1개)
self.tail = None # tail 삭제
else: # 노드가 2개 이상일 때
self.tail.link = self.tail.link.link # front = front의 다음 노드
return data # 이전의 front 데이터 반환

def size(self):
if self.isEmpty(): return 0
else:
count = 1 # 1부터 시작
node = self.tail.link # front 부터 출발
while not node == self.tail: # node가 rear가 아닌 동안
node = node.link # 다음 노드로 이동
count += 1 # count 증가
return count
def display(self, msg=`CircularLinkedQueue`):
print(msg, end="")
if not self.isEmpty():
node = self.tail.link # front 부터 시작
while not node == self.tail: # rear를 만날 때 까지
print(node.data, end=" ")
node = node.link
print(node.data, end=" ") # 마지막 노드의 항목 출력
print()
class DNode:
def __init__(self, elem, prev = None, next = None):
self.data = elem
self.prev = prev
self.next = nextclass DoublyLinkedDeque:
def __init__(self):
self.front = None
self.rear = None
def isEmpty(self): return self.front == None # front가 None이면 공백
def clear(self): self.front = self.rear = None # 전부 초기화
def size(self):
node = self.front # front에서 시작
count = 0
while not node == None: # 노드가 None이 될 때 까지
node = node.next # 다음 노드로 이동
count += 1 # count 증가
return count
def display(self, msg=`LinkedStack : `):
print(msg, end="")
node = self.front # front에서 시작
while not node == None: # 노드가 없을 때 까지
print(node.data, end=' ') # 노드 출력
node = node.next # 다음 노드로 이동
print()def addFront(self, item):
node = Dnode(item, None, self.front)
if self.isEmpty(): # 공백이면
self.front = self.rear = node # front와 rear가 모두 node
else:
self.front.prev = node # front의 이전값이 node
self.front = node # front 값이 node
def addRear(self, item):
node = Dnode(item, self.rear, None)
if self.isEmpty(): # 공백이면
self.front = self.rear = node # front와 rear가 전부 새 노드
else:
self.rear.next = node # rear의 다음 값 = node
self.rear = node # rear를 node로 변경def deleteFront(self):
if not self.isEmpty(): # 공백이 아닐 때
data = self.front.data # data에 front 값 복사
self.front = self.front.next # front를 다음 노드로 변경
if self.front = None: # 노드가 하나 뿐이면
self.rear = None # rear도 None으로 변경
else:
self.front.prev = None # front의 이전노드 제거
return datadef deleteRear(self):
if not self.isEmpty(): # 공백이 아닐 때
data = self.rear.data # data에 rear 값 복사
self.rear = self.rear.prev # rear를 이전 노드로 변경
if self.rear = None: # 노드가 하나 뿐이면
self.front = None
else:
self.rear.next = None # rear 다음 노드 제거
return data 앱과 웹을 만들고, 직접 운영하며 기록합니다.
giscus로 동작하며 GitHub Discussions에 저장됩니다.