[파이썬 | 자료구조] 5. 연결 리스트(Linked List)

5. 연결 리스트(Linked List)

Python에서 사용하는 List의 기본적인 구조는 Linked List이다

다른 C나 Java의 경우 기초 프로그래밍을 할 때 배열을 이용하게 되지만 파이썬에서는 배열이 없는 이유가 Linked List를 기본적으로 지원하기 때문이다

연결 리스트라고 하는 Linked List는 배열과 달리 내부 메모리 주소적으로 봤을때 연속된 주소가 아니라, 서로 떨어진 데이터를 주소를 연결하여 관리하는 데이터 구조이다.

따라서 미리 데이터 공간을 할당할 필요가 없다는 장점이 있지만

데이터 검색효율이 안좋으며, 데이터 삭제시 양쪽의 node를 이어주는 등의 구현에서 불편함 등의 단점이 있다.

 

	# mynode.py
	class node:
	def __init__(self, item):
	self.data = item
	self.next = None
	def setData(self, item):
	self.data = item
	def setNext(self, target):
	self.next = target

view raw mynode.py hosted with ❤ by GitHub

Single Linked List

	from mynode import node # mynode.py 파일에서 node class를 불러옴
	class myLinkedList:
	def __init__(self):
	dummy = node(None)
	self.head = dummy # head에 dummy node를 하나 만들어놓는것이 구현에서 유리하다
	def add(self, item):
	newNode = node(item) # 새로운 node 생성
	horse = self.head # head를 움직이면 안되니, 탐색용 node인 horse생성
	while horse.next: # 맨 끝으로 horse를 보내고
	horse = horse.next
	horse.next = newNode # 맨 끝에 새로운 node를 추가한다.
	def pop(self):
	horse = self.head
	turtle = self.head # turtle은 horse보다 한 칸 앞의 node를 가리킨다.
	while horse.next:
	turtle = horse
	horse = horse.next
	ret = horse.data # turtle이 필요한 이유는, horse를 지워버리게 되면
	turtle.next = None # horse를 가리키던 이전 node(turtle)의 next가 쓰레기값을 갖는다
	return ret # turtle의 next를 None으로 재할당
	def delete(self, item):
	horse = self.head
	turtle = self.head
	while horse.next:
	if horse.data == item:
	turtle.next = horse.next
	del horse
	return
	turtle = horse
	horse = horse.next
	if horse.data == item:
	turtle.next = horse.next
	del horse
	return
	def getAll(self):
	ret = []
	horse = self.head
	while horse.next:
	ret.append(horse.data)
	horse = horse.next
	ret.append(horse.data)
	return ret[1:] # Dummy node 제외
	ll = myLinkedList()
	ll.add(1) # 노드 1 리스트에 추가
	ll.add(2) # 노드 2 리스트에 추가
	ll.add(3) # 노드 3 리스트에 추가
	print(ll.getAll()) # 1 2 3 출력
	ll.delete(2) # 노드 2 삭제
	print(ll.getAll()) # 1 3 출력
	ll.delete(1) # 노드 1 삭제
	print(ll.getAll()) # 3 출력
	ll.delete(3) # 노드 3 삭제
	# [1, 2, 3]
	# [1, 3]
	# [3]

view raw linkedlist2.py hosted with ❤ by GitHub

Double LInked List

Single Linked List에서 서로의 노드를 양쪽 모두 연결한다.

Single과는 달리 양쪽으로 탐색이 가능하다는 장점이 있다.

	from mynode import node
	from collections import deque
	class myDoubleLinkedList:
	def __init__(self):
	dummy = node(None)
	self.head = dummy # head에 dummy node를 하나 만들어놓는것이 구현에서 유리하다
	self.tail = dummy
	def add(self, item):
	newNode = node(item) # tail에 새로운 노드를 추가하고 prev, next 관계를 update
	self.tail.next = newNode
	newNode.prev = self.tail
	self.tail = newNode
	def pop(self):
	delNode = self.tail # tail을 이전으로 옮기고 노드를 삭제한다.
	self.tail = delNode.prev
	self.tail.next = None
	del delNode
	def delete(self, item):
	horse = self.head
	while horse.next:
	if horse.data == item:
	horse.prev.next = horse.next
	horse.next.prev = horse.prev
	del horse
	return
	horse = horse.next
	if horse.data == item:
	horse.prev.next = None
	self.tail = horse.prev
	del horse
	return
	def getAll(self):
	ret1 = []
	ret2 = []
	horse1 = self.head
	horse2 = self.tail
	# Double Linked List는 양방향으로 탐색할 수 있다.
	while horse1.next and horse2.prev and horse1 != horse2 and horse1.next != horse2:
	ret1.append(horse1.data)
	ret2.append(horse2.data)
	horse1 = horse1.next
	horse2 = horse2.prev
	if horse1 == horse2:
	ret1.append(horse1.data)
	else:
	ret1.append(horse1.data)
	ret2.append(horse2.data)
	ret = ret1[1:] + ret2[::-1]
	return ret # Dummy node 제외
	dll = myDoubleLinkedList()
	dll.add(1)
	dll.add(2)
	dll.add(3)
	dll.add(4)
	dll.add(5)
	dll.delete(4)
	print(dll.getAll()) # [1, 2, 3, 5]
	dll.pop()
	print(dll.getAll()) # [1, 2, 3]
	dll.delete(2)
	print(dll.getAll()) # [1, 3]
	dll.pop()
	print(dll.getAll()) # [1]

view raw linkedlist3.py hosted with ❤ by GitHub