💾 linked_list, queue, stack

S5-Week 2 : Data Structure and Algorithm Core (2)

추상 자료형 Abstract Data Type

컬렉션 자료형(list, tuple, dict, set..)에 대해서 배웠는데 추상 자료형이란?

• 추상적으로 필요한 기능을 나열한 로직으로 (명세서)
• linked-list, queue, stack, tree 등이 있다
• 컴퓨터에 자료를 저장하는 구조의 로직을 코드로 나타내보는 것!
• 기본 자료형(list, integer, string)을 활용하여 사용자에 의해 구현됨

파이썬의 리스트는 배열과 연결리스트의 특징 모두 갖고 있다.

Linked-list(연결 리스트)

• 쉽게 말해 노드들을 연결한 형태의 자료형
• 길이가 정해지지 않은 데이터를 저장할 때 배열보다 좋다
• 지금까지 인덱스 중심적으로 개발하면 불편한 점이 있다
  - 데이터를 추가하거나, 삭제할때..
  • 배열의 크기를 한번 정하면 늘이거나 줄일 수 없다
  • 그래서 메모리를 유동적으로 사용해보자
  • 인덱스에 얽매이지 말자 해서 개발된 것
• 연결은 프로그래밍에서 참조의 기능으로 구현되고, 연결리스트는 리스트의 길이(인덱스)를 별도로 지정해줄 필요가 없다.
  - 따라서 인덱스가 없다
  - 값만 있다 (다음 위치의 노드 주소값이랑)
  - head - tail
  - 노드를 연결하며 인덱스를 확장해준다

  배열 : 요소를 직접 접근하여 저장하고 인덱스 활용
  연결리스트 : 각 요소는 참조하는 노드에 저장된다

• 각 노드는 연결 리스트의 다음 노드에 대해 참조(또는 포인터)를 한다
  • 참조 : . >> head.next 헤드 노드가 next를 참조

# linked list 객체 만들기
# linked list의 단위인 노드 객체 먼저 만들기
# 노드에는 값과 다음 노드로 향하는 포인터 (주소) 값이 있다

class Node:
	def __init__(self, value, next=None):
		self.value = value
		self.next = next # 노드의 다음 위치를 가리키는 next의 초기 값은 None

# linked list 객체 만들기
# 헤드의 값을 선언하면서 시작
class linked_list:
	def __init__(self, value):
		self.head = Node(value)
	# 노드를 추가하는 메쏘드도 있답니다
	def add_node(value):
		# 첫번째 위치에 해당하는 head를
		# node 변수에 저장
		node = head
		while head.next: # 여기가 왜 while이냐?
			node = head.next 
			print(head.next)
		node.next = Node(value) 

head = Node(1)
linked_list.add_node(3)

print(head)
print(head.next)
print(head.value)
print(head.next.value)

>> <__main__.Node object at 0x10b4e3af0>
>> <__main__.Node object at 0x10b4e36a0>
>> 1
>> 3

• head 노드와 head.next 값엔 노드의 위치 (주소)값이 있는 것을 알 수 있음.
• head 노드와 head.next 노드의 value 속성 값엔 1, 3이 들어있음.
• 연결한다는 것은 곧 참조되는 노드의 위치를 바꾸는 것 (주소)

linked_list는 반복문이 있어야 연결이 된다

node1 = Node(3)
node2 = Node(4)

node3 = Node(5)
node4 = Node(6)

node1.next = node2 # node2의 값은 node1을 참조한다
# node1 -> node2
node2.next = node3
node3.next = node4

node = node1 # node 변수에 node1 값으로 시작 - 헤드
while node: # node에 값이 있다면 연결 리스트를 쭉 돌아라 (반복)
  print(node.value)
  node = node.next # 마치 while 문에서 p++ 하는 것처럼

새로운 node 중간에 넣는 경우

# node2 -> node5 -> node3

node5 = Node(7)

node2.next = node5
node5.next = node3

연결리스트도 리스트의 메소드와 같은 기능들을 구현할 수 있다.

• 삽입
• 삭제
• 검색

class Node:
	def __init__(self, value, next=None):
		self.value = value
		self.next = next
class linked_list:
	def __init__(self, value):
		self.head = Node(value) # 헤드를 생성하는 연결 리스트 속성
	# node에 접근하는 방법은 head -> tail까지 반복문을 통해 접근하는 것
	def add_node(self, value):
		if self.head == None: # 헤드가 없으면
			self.head = Node(value) # 헤드 생성해줘라 (add node 역할)
		else : # 시작할 헤드가 있다면
			node = self.head # node 변수에 헤드 넣어놓고
			while node.next: # 그 다음 값이 있을 때까지 계속
				node = node.next # node 끝까지 돌리기
			# tail node로 도착했다면
			node.next = Node(value) # 새로운 tail node 추가
	def del_node(self, value):
		if self.head == None: # 헤드가 없으면 
			print("해당 값에 대한 노드는 없다")
			return # 아무것도 반환 x
		elif self.head.value == value : # 헤드의 value가 삭제하고자 하는 value라면
			# 우선 값을 삭제해주기 위해 temp_node로 값 복사
			temp_node = self.head
			# 헤드 노드를 헤드의 다음 노드로 변경 (헤드는 늘 시작하는 노드)
			self.head = self.head.next
			# 그리고 temp_node는 삭제
			del temp_node
		else: # 헤드가 아닌 노드의 값을 삭제하는 경우
			# 그 노드를 반복문으로 찾는다
			node = self.head
			while node.next:
				if node.next.value == value:
					temp_node = node.next
					# node.next 자리에는 node.next.next 넣어주기
					node.next = node.next.next
					del temp_node
				else:
					node = node.next
	# 노드 출력 (내림차순)
	def ord_desc(self):
		node = self.head
		while node:
			print(node.value)
			node = node.next
            
    	# 연결리스트 검색함수
        def	search_node(self, value):
		node = self.head
		while node:
			if node.value == value:
				return node
			else:
				node = node.next

# 연결리스트의 head의 주소를 확인함으로써 메모리상에 연결리스트가 존재함을 확인
linkedlist.head
>>> <__main__.Node at 0x10aa6ec40>

• head를 삭제하는 것은 head 노드 자체를 삭제하는 것이 아니라, head node 다음 node가 head가 될 수 있도록 노드의 위치를 바꿔주는 것