📒 자료형과 자료구조
- 자료형 : 어떤 자료가 식별될 수 있는 방법과 그 자료에 대한 여러가지 연산을 결정하는 것으로, 자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와 그 구현을 의미한다.
👉 추상적 자료형 : 자료들과 그 자료에 대한 연산들을 명시한 것(구현 방법을 명시하고 있지 않다.)- 자료구조 : 자료를 저장하는 구조로, 추상적 자료형을 구체적으로 정의한 결과
추상적 자료형 예시
1) 추상적 자료형 : 리스트
2) 자료구조 : 배열, 연결리스트 등등...
🍑 연결리스트(Linked List)
추상적 자료형인 '리스트'를 구현한 자료구조, 노드와 포인터로 이루어져 있다.
👉 노드는 자료의 값, 포인터는 자신의 다음 순서 노드를 가리킨다
- 어떠한 데이터를 저장할 때 그 다음 순서의 자료가 있는 위치에 데이터를 포함시켜 자료를 저장한다. 이 때, 저장되는 데이터는 노드(node), 그 다음 데이터는 포인터(pointer)가 된다.
- 크게 단순 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)로 나눌 수 있다.
🧩 장점
- 자료의 추가와 삭제가 편한다.
👉 최악의 경우 O(n)의 시간 복잡도를 갖지만, 기본적으로는 O(1)이다.(들어갈 위치를 찾아서 선을 긋기만 하면 된다!)
🙈 단점
- 특정 위치의 자료를 찾는 것이 번거롭다.
- 자료의 위치가 시작점에서 멀수록 연산 횟수가 증가한다.
장단점 정리
'배열'과 비교해 보면 배열은 배열 내의 특정 순서의 값을 조회하고자 할 때 단번에 찾아낼 수 있지만 자료를 추가할 때는 조금 번거롭다는 단점이 있다. 즉, 새로운 자료가 추가되면서 자료들의 순서를 변경해 주어야 한다는 단점이 있는데 반해 연결리스트는 새로운 자료의 추가(또는 삭제)가 비교적 편하다는 장점이 있다.
🍓 연결리스트의 종류
-
단순 연결 리스트 : 가장 단순한 형태의 연결리스트로, 다음 노드에 대한 참조만을 가진다. 가장 마지막 원소를 찾기 위해서는 리스트 끝까지 찾아가야 한다는 단점이 있다. 보통 큐를 구현할 때 사용한다.
👉 단순 연결 리스트는 Head 노드를 참조하는 주소를 잃어버리게 되면 전체 데이터를 못 쓰게 되는 단점이 있다. -
이중 연결 리스트 : 다음 노드의 참조 뿐만 아니라 이전 노드의 참조도 같이 가리키는 연결 리스트이다.
👉 단순 연결 리스트는 삽입 또는 삭제시 반드시 이전 노드를 가리키는 참조를 추가로 알아야 한다는 단점이 있지만 이중 연결 리스트는 현재 노드를 삭제하는 것이 훨씬 간단함 -
원형 연결 리스트 : 단순 연결 리스트에서 마지막 원소는 Null을 가리키는데, 만약 이 대신 '처음 노드'를 가리키게 한 것이 원형 연결 리스트이다.
🥝 연결 리스트 구현
[이중 연결 리스트 : python으로 구현]
class Node:
def __init__(self, data, prev, next):
self.data = data
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.head = Node(None, None, None)
self.tail = Node(None, self.head, None)
self.head.next = self.tail
self.length = 0
def size(self):
return self.length
def is_empty(self):
if self.length == 0:
return True
else:
return False
# present가 가리키는 이전 노드 앞에 새로운 노드 삽입
def insert_before(self, present, data):
old = present.prev # 이전 노드
new_node = Node(data, old, present)
# 현재 노드의 이전 노드에 새로운 노드 추가
present.prev = new_node
old.next = new_node
self.length += 1
# present가 가리키는 다음 노드 앞에 새로운 노드 삽입
def insert_after(self, present, data):
old = present.next
new_node = Node(data, present, old)
old.prev = new_node
present.next = new_node
self.length += 1
# 노드 n 삭제
def delete(self, n):
if self.is_empty():
return "빈 리스트입니다."
front = n.prev # 앞 노드
rear = n.next # 뒷 노드
front.next = rear
rear.prev = front
self.length -= 1
return n.data
# 데이터 검색 : head부터
def search_from_head(self, data):
if self.head == None:
return False
node = self.head
while node:
# 데이터 일치할 경우 True 리턴
if node.data == data:
return True
else:
node = node.next
return False
# 데이터 검색 : tail부터
def search_from_tail(self, data):
if self.head == None:
return False
node = self.tail
while node:
if node.data == data:
return True
else:
node = node.prev
return False
# 리스트 출력
def get_list(self):
result = []
current = self.head
while current != None:
result.append(current.data)
current = current.next
return result참조(References)
1)연결리스트의 종류
