4-3. 원형 연결 리스트

연결 리스트에 대한 내용은 여기에 있다.

4-1. 한방향 연결 리스트

 

1. 원형 연결 리스트

 원형 연결 리스트(Circular Linked List)는 노드들이 원형으로 연결된 리스트이다.

원형 연결 리스트

 위 그림과 같이 한방향 연결 리스트의 tail의 next를 head로 연결하면 원형 연결 리스트가 된다. 아래 그림도 보자.

원형 연결 리스트

 이 그림을 통해 볼 수 있는 원형 연결 리스트의 특징은 다음과 같다.

• 리스트의 시작과 끝 개념이 없다.
• 노드 간에 순서 관계를 부여하기 위해 특정 노드의 레퍼런스를 current로 둔다.
• current = current.next로 리스트를 순회한다.

이런 원형 연결 리스트는 라운드 로빈 스케줄러에 사용되는데, 라운드 로빈 스케줄러란 여러 클라이언트가 자원이나 서비스를 공유할 때 순차적으로 돌아가면서 서비스를 이용하는 형태를 말한다.

 

2. 원형 연결 리스트 구현하기

 파이썬으로 CircularQueue 클래스를 구현해보자.

class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class CircularQueue:
	"""Queue implementation using circularly linked list for storage."""
    
    class _Node:
		"Lightweight, nonpublic class for storing a singly linked node."""
		__slots__ = '_element', '_next'			# streamline memory usage

		def __init__(self, element, next):
			self._element = element
			self._next = next

	def __init__(self):
		"""Create an empty queue."""
		self._tail = None				# will represent tail of queue
		self._size = 0					# number of queue elements

	def __len__(self):
		"""Return the number of elements in the queue."""
		return self._size
        
	def is_empty(self):
		"""Return True if the queue is_empty."""
		return self._size == 0
        
	def first(self):
		"""Return (but do not remove) the element at the front of the queue.
        Raise Empty exception if the queue is_empty."""
		if self.is_empty():
			raise Empty('Queue is_empty')
		head = self._tail._next
		return head._element

	def dequeue(self):
		"""Remove and return the first element of the queue (i.e., FIFO).
        Raise Empty exception if the queue is_empty."""
		if self.is_empty():
			raise Empty('Queue is_empty')
		oldhead = self._tail._next
		if self._size == 1:				# removing only element
			self._tail = None			# queue becomes empty
		else:
			self._tail._next = oldhead._next	# bypass the old head
		self._size -= 1
		return oldhead._element
        
	def enqueue(self, e):
		"""Add an element to the back of queue."""
		newest = self._Node(e, None)			# node will be new tail node
		if self.is_empty():
			newest._next = newest			# initialize circularly
		else:
			newest._tail = self._tail._next		# new node points to head
			self._tail._next = newest		# old tail points to new node
		self._tail = newest
		self._size += 1
        
	def rotate(self):
		"""Rotate front element to the back of the queue."""
		if self._size > 0:
			self._tail = self._tail._next		# old head becomes new tail

---

1) 클래스 선언

class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class CircularQueue:
	"""Queue implementation using circularly linked list for storage."""

 

2) Node 클래스 선언(Nested Class): Node 클래스를 외부에 보이지 않도록 nonpublic class로 선언

    class _Node:
		"Lightweight, nonpublic class for storing a singly linked node."""
		__slots__ = '_element', '_next'			# streamline memory usage

		def __init__(self, element, next):
			self._element = element
			self._next = next

 

3) 초기화

• self._tail: tail node 관리(단, head는 별도로 관리하지 않음)
• self._size: 큐에 저장된 데이터 개수

	def __init__(self):
		"""Create an empty queue."""
		self._tail = None				# will represent tail of queue
		self._size = 0					# number of queue elements

 

4) 길이: self._size를 return

	def __len__(self):
		"""Return the number of elements in the queue."""
		return self._size

 

5) 큐가 비어 있는지 확인: self._size가 0이면 True, 아니면 False

	def is_empty(self):
		"""Return True if the queue is_empty."""
		return self._size == 0

 

6) 큐의 첫 번째 요소를 반환

• 큐가 비어 있으면 Empty exception 발생
• tail의 다음 요소로 head를 구함
• 큐가 비어 있지 않으면 head의 요소를 반환 

	def first(self):
		"""Return (but do not remove) the element at the front of the queue.
        Raise Empty exception if the queue is_empty."""
		if self.is_empty():
			raise Empty('Queue is_empty')
		head = self._tail._next
		return head._element

 

7) dequeue

 : LinkedQueue의 dequeue와 순서만 다르고 논리적으로 동일!

  단, CircularQueue의 경우 head가 없으므로 oldhead를 만들어 사용한 점이 다르다.

• 큐가 비어 있으면 Empty exception 발생
• head의 요소를 반환하기 위해 tail로부터 head를 구함
• 큐에 남아 있는 요소가 1개라면 tail을 None으로 지정
• 큐에 남아 있는 요소가 2개 이상이라면 tail과 head의 다음 노드를 연결
• 크기는 1을 줄임

	def dequeue(self):
		"""Remove and return the first element of the queue (i.e., FIFO).
        Raise Empty exception if the queue is_empty."""
		if self.is_empty():
			raise Empty('Queue is_empty')
		oldhead = self._tail._next
		if self._size == 1:				# removing only element
			self._tail = None			# queue becomes empty
		else:
			self._tail._next = oldhead._next	# bypass the old head
		self._size -= 1
		return oldhead._element

 

8) enqueue

 : CircularQueue의 경우 새로운 노드의 링크를 원형으로 설정해주는 부분이 더 있음.

• 새로운 노드를 생성
• 큐가 비어 있으면 새로운 노드의 바로 다음 노드를 자기 자신으로 지정
• 큐가 비어 있지 않으면 새로운 노드를 tail의 뒤에 연결
• tail을 새로운 노드로 이동하고 크기를 1 늘림

	def enqueue(self, e):
		"""Add an element to the back of queue."""
		newest = self._Node(e, None)			# node will be new tail node
		if self.is_empty():
			newest._next = newest			# initialize circularly
		else:
			newest._tail = self._tail._next		# new node points to head
			self._tail._next = newest		# old tail points to new node
		self._tail = newest
		self._size += 1

 

9) 회전: 큐가 비어 있지 않으면  tail을 다음 노드로 이동

	def rotate(self):
		"""Rotate front element to the back of the queue."""
		if self._size > 0:
			self._tail = self._tail._next		# old head becomes new tail

 

다음 게시글부터는 양방향 연결 리스트에 대해 다룬다.