데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리방식
목적 -> 자료를 구조화하여 데이터를 효율적으로 사용하기 위해
스토리지 : 데이터가 영구적으로 저장되는 곳. 데이터를 저장하고 받아오는데에 오래걸림
메모리 : 데이터가 임시로 저장되는 곳. 데이터를 저장하고 받아오는데에 빠름
RAM : 임의접근 메모리.
임의접근 - 저장 위치를 알면 접근할 때 항상 일정한 시간이 걸림(시간복잡도 O(1))
순차접근 - 저장된 위치까지 가는데 한단계씩 거쳐야 함
-> 임의접근이 순차접근보다 훨씬 효율적
레퍼런스(reference)
데이터에 접근할 수 있게 해주는 값
'주소'보다 조금 더 포괄적인 개념
자료구조를 배울때에는 주소=레퍼런스 라고 생각해도 됨
인덱스 접근 - O(1)
선형탐색(순서대로 탐색하는 것) - O(n)
정적배열
크기 고정(요소수 제한)
동적배열
크기 변함(요소 계속 추가 가능). 정적배열로 만들어진 자료구조. 정적배열의 크기를 상황에 맞게 조절
추가 연산 시간 복잡도 : 최고의 경우(내부배열에 빈공간이 있을 때. 자주일어남) O(1), 최악의 경우(내부배열에 빈공간이 없을 때. 가끔 일어남) O(n)
❗️ 분할상환분석 ( 할부라고 생각하면 됨)
시간분석도를 최악의 경우를 얘기하지 않고 평균을 내어 얘기함. 같은 동작을 n번 했을 때 드는 시간이 x일때 -> 동작을 한번 하는데 걸린시간 : x/n
따라서, 동적배열의 추가연산 시간복잡도는 최악의 경우 O(n)이며 분할 상환 분석을 하면 O(1)이 걸린다
삽입연산시간복잡도 : O(n)
삭제연산시간복잡도 : 아무 위치에 있는 데이터를 삭제할 때는 최악의 경우 O(n). 가장 뒤에 있는 데이터를 삭제할 때는 최악의 경우 O(n)이 걸리지만 분할 상환 분석을 적용하면 O(1).
데이터를 순서대로 저장해준다.
요소를 계속 추가할 수 있다.
노드 1개에 데이터값과 다음노드의 주소값이 저장되어 있어서 서로 연결
Head node 만 알면 주소값을 타고 타고 모든 노드들을 알 수 있다.
시간 복잡도 : 접근 O(n) / 탐색 O(n) / 삽입 O(n) / 삭제 O(n)
❗️ 가장앞에 삽입, 가장 앞 노드 삭제, 가장 뒤에 삽입 -> O(1) / 가장 뒤 노드 삭제 O(n)
class Node:
"""링크드 리스트의 노드 클래스"""
def __init__(self, data):
self.data = data # 노드가 저장하는 데이터
self.next = None # 다음 노드에 대한 래퍼런스
class LinkedList:
"""링크드 리스트 클래스"""
def __init__(self):
self.head = None
self.tail = None
def insert_after(self, previous_node, data):
"""링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
new_node = Node(data)
if previous_node is self.tail:
self.tail.next = new_node
self.tail = new_node
else:
new_node.next = previous_node.next
previous_node.next = new_node
def delete_after(self, previous_node):
"""링크드 리스트 주어진 노드 뒤 삭제 연산 """
data = previous_node.next.data # 링크 리스트의 데이터를 삭제할때는 지워주는 데이터를 리턴해주는게 관습.
if previous_node is self.tail:
previous_node.next = None
self.tail = previous_node
else:
previous_node.next = previous_node.next.next
return data
def find_node_at(self, index):
"""링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""
iterator = self.head
for _ in range(index):
iterator = iterator.next
return iterator
def append(self, data):
"""링크드 리스트 추가 연산 메소드"""
new_node = Node(data)
if self.head is None: # 링크드 리스트가 비어있는 경우
self.head = new_node
self.tail = new_node
else: # 링크드 리스트가 비어 있지 않은 경우
self.tail.next = new_node
self.tail = new_node
def __str__(self): # 자동으로 내용을 사람들이 이해할 수 있는 문자열로 리턴해주는 메소드
"""링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
res_str = "|"
iterator = self.head
while iterator is not None:
# 각 노드의 데이터를 리턴하는 문자열에 더해준다
res_str += f" {iterator.data} |"
iterator = iterator.next # 다음노드로 넘어간다
return res_str