4-6. 포지션 리스트

4-4. 양방향 연결 리스트

1. 연결 리스트의 위치 식별 방법

연결 리스트에서 인덱스로 위치를 식별하면 좋을까?

연결 리스트를 인덱스로 접근한다면?

 - 좋지 않다. 연결 리스트를 인덱스로 접근하려면 반복적으로 탐색해야 하므로 효율적으로 처리할 수 없으며, 연결 리스트가 바뀔 때마다 인덱스가 달라질 수 있다. 즉, 비효율적이다.

 

연결 리스트에서 직접 노드로 위치를 식별하게 하면 어떨까?

연결 리스트의 위치를 노드로 식별한다면?

 - 노드는 내부 클래스로 은닉시켜 둔 상태이므로 외부로 노출하는 것은 객체 지향 설계 사상에 위배된다.

 

그렇다면 왜 노드를 내부 클래스에 은닉했을까?

• 단순함(Simplicity): 구현에 대한 세부 내용은 숨기고 간단한 형태로 노출할 수 있다.
• 무결성(Robustness): 노드에 직접 접근하지 못하도록 하여 연결 리스트의 일관성을 유지할 수 있다.
• 유연성(Flexibility): 자유롭게 설계와 구현을 변경할 수 있다. 자료구조를 재설계하여 성능 개선이 가능하다.

 

요소의 위치를 표현하는 객체를 통해 접근하도록 하면 어떨까?

포지션 리스트

 - 리스트에서 노드의 위치를 나타내며 토큰과 같이 행동하게 하면 가능하다. 리스트의 변화에 영향을 받지 않으며, 내부적으로 노드를 참조하고 있어 노드를 통해 리스트 이동이 가능하기 때문이다.

 

2. 순회

 리스트 클래스 외부에서도 위치(Position)을 기반으로 리스트를 순회할 수 있다.

 

1) 순회: first()와 after() 함수를 이용해 위치를 다음 노드로 이동, 리스트의 마지막 노드에 도달하면 None을 반환

cursor = data.first()
while cursor is not None:
	print(cursor.element())				# print the element stored at the position
	cursor = data.after(cursor)			# advance to the next position (if any)

 

2) for loop 방식 순회: __iter__함수를 통해 generator로 정의해 for loop 형식으로도 순회 가능.

for e in data:
	print(e)

 

3. 포지션 리스트의 연산

• 접근 연산(Accessor Method)

첫번째 위치	L.first()	- 리스트의 첫번째 요소의 위치 반환 - 리스트가 비었으면 None을 반환
마지막 위치	L.last()	- 리스트의 마지막 요소의 위치 반환 - 리스트가 비었으면 None을 반환
이전 위치	L.before(p)	- 위치 p의 이전 위치 반환 - 위치 p가 첫번째 위치면 None을 반환
다음 위치	L.after(p)	- 위치 p의 다음 위치 반환 - 위치 p가 마지막 위치면 None을 반환
비었는지 체크	L.is_empty()	리스트에 요소가 없으면 True 반환
개수	len(L)	리스트에 저장된 요소의 개수 반환
순서대로 조회	iter(L)	리스트의 요소에 대한 generator 정의

 

• 업데이트 연산(Update Method)

처음에 추가	L.add_first(e)	리스트의 맨 처음에 새로운 요소 e를 추가하고 위치 반환
마지막에 추가	L.add_last(e)	리스트의 끝에 새로운 요소 e를 추가하고 위치 반환
이전에 추가	L.add_before(p, e)	위치 p의 이전 위치에 새로운 요소 e를 추가하고 위치 반환
다음에 추가	L.add_after(p, e)	위치 p의 다음 위치에 새로운 요소 e를 추가하고 위치 반환
대체	L.replace(p, e)	위치 p의 요소 e를 대체하고 이전에 p에 저장되었던 요소를 반환
삭제	L.delete(p)	위치 p의 요소를 삭제하고 반환하면 위치 p를 invalidate

 

4. 포지션 리스트 구현

 양방향 연결 리스트로 포지션 리스트를 구현하면 모든 연산이 최악의 경우 O(1) 시간 복잡도를 갖는다.

포지션 리스트(PositionList) = 양방향 연결 리스트(_DoublyLinkedList) + Position 기반의 접근 및 업데이트 연산

• PositionList의 대부분의 메소드는 노드를 참조하는 Position 인스턴스를 반환하면 종료된다.
• Position 인스턴스 간에 p == q와 같은 형태의 연산을 지원하기 위해 __ne__, __eq__ 메소드를 정의한다.

 

5. PositionList 클래스

class PositionList(_DoublyLinkedBase):
	"""A sequential container of elements allowing positional class."""
    
	class Position:
		"""An abstraction representing the location of a single element."""
		
		def __init(self):
			"""Constructor should nor be invoked by user."""
			self._container = container
			self._node = node

		def element(self):
			"""Return the element stored at this Position."""
			return self._node._element

		def __eq__(self, other):
			"""Return True if other is a Position representing the same location."""
			return type(other) is type(self) and other._node is self._node

		def __ne__(self, other):
			"""Return True if other does not represent the same location."""
			return not (self == other)			# opposite of __eq__

	def _validate(self, p):
		"""Return position's node, or raise appropriate error if invalid."""
		if not isinstance(p, self.Position):
			raise TypeError('p must be proper Position type')
		if p._container is not self:
			raise ValueError('p does not belong to this container')
		if p._node._next is None:				# convention for deprecated nodes
			raise ValueError('p is not longer valid')
		return p._node
        
	def _make_position(self, node):
		"""Return Position instance for given node (or None if sentinel)."""
		if node is self._header or node is self._trailer	# boundary violation
			return None
		else:
			return self.Position(self, node)		# legitimate position

	def first(self):
		"""Return the first Position in the list (or None if list is empty)."""
		return self._make_position(self._header._next)

	def last(self):
		"""Return the last Position in the list (or None if list is empty)."""
		return self._make_position(self._trailer._prev)

	def before(self, p):
		"""Return the Position just before Position p (or None if p is first)."""
		node = self._validate(p)
		return self._make_position(node._prev)
        
	def after(self, p):
		"""Return the Position just after Position p (or None if p is last)."""
		node = self._validate(p)
		return self._make_position(node._next)
        
	def __iter__(self):
		"""Generate a forward iteration of the elements of the list."""
		cursor = self.first()
		while cursor is not None:
			yield cursor.element()
			cursor = self.after(cursor)

	def _insert_between(self, e, predecssor, successor):
		"""Add element between existing nodes and return new Position."""
		node = super()._insert_between(e, predecessor, successor)
		return self._make_position(node)
        
	def add_first(self, e):
		"""Insert element e at the front of the list and return new Position."""
		return self._insert_between(e, self._header, self._header._next)
        
	def add_last(self, e):
		"""Insert element e at the back of the list and return new Position."""
		return self._insert_between(e, self._trailer._prev, self._trailer)

	def add_before(self, p, e):
		"""Insert element e into list before Position p and return new Position."""
		original = self._validate(p)
		return self._insert_between(e, original._prev, original)

	def add_after(self, p, e):
		"""Insert element e into list after Position p and return new Position."""
		original = self._validate(p)
		return self._insert_between(e, original, original._next)

	def delete(self, p):
		"""Remove and return the element at Position p."""
		original = self._validate(p)
		return self._delete_node(original)			# inherited method returns element

	def replace(self, p, e):
		"""Replace the element at Position p with e.
        Return the element formerly at Position p."""
		original = self._validate(p)
		old_value = original._element				# temporarily store old element
		original._element = e				 	# replace with new element
		return old_value

---

PositionList 클래스

1) 클래스 선언: _DoublyLinkedBase에서 상속받음.

class PositionList(_DoublyLinkedBase):
	"""A sequential container of elements allowing positional class."""

---

Position 클래스

1) 클래스 선언: PositionList의 클래스의 Internal 클래스로 선언됨.

	class Position:
		"""An abstraction representing the location of a single element."""

 

2) 초기화

• _container: PositionList의 레퍼런스
• _node: Node의 레퍼런스

		def __init(self):
			"""Constructor should nor be invoked by user."""
			self._container = container
			self._node = node

 

3) 위치가 가리키는 노드의 요소를 반환

		def element(self):
			"""Return the element stored at this Position."""
			return self._node._element

 

4) 두 위치가 같은지 판별: 비교할 위치 other과 타입과 참조 노드가 동일하면 같은 위치로 판별

		def __eq__(self, other):
			"""Return True if other is a Position representing the same location."""
			return type(other) is type(self) and other._node is self._node

 

5) 두 위치가 다른지 판별: 두 위치가 같지 않으면 True 반환

		def __ne__(self, other):
			"""Return True if other does not represent the same location."""
			return not (self == other)			# opposite of __eq__

---

PositionList 클래스

2) 유효한 위치인지 확인

• 위치가 Position 클래스의 인스턴스인지 확인
• 위치의 컨테이너 PositionList가 자신인지 확인 (내가 관리하는 연결 리스트의 위치인지 확인)
• 위치가 가리키는 노드가 폐기된 노드인지 확인 (_prev, _next가 None이면 deprecated node임.)

	def _validate(self, p):
		"""Return position's node, or raise appropriate error if invalid."""
		if not isinstance(p, self.Position):
			raise TypeError('p must be proper Position type')
		if p._container is not self:
			raise ValueError('p does not belong to this container')
		if p._node._next is None:				# convention for deprecated nodes
			raise ValueError('p is not longer valid')
		return p._node

 

3) 노드에 대한 위치 생성

• 노드가 header 또는 trailer이면 None을 반환
• 노드가 header 또는 trailer가 아니라면 Position 객체를 생성해서 반환

	def _make_position(self, node):
		"""Return Position instance for given node (or None if sentinel)."""
		if node is self._header or node is self._trailer	# boundary violation
			return None
		else:
			return self.Position(self, node)		# legitimate position

 

4) 첫번째 요소의 위치: 첫번째 노드는 항상 header의 다음 노드임

	def first(self):
		"""Return the first Position in the list (or None if list is empty)."""
		return self._make_position(self._header._next)

 

5) 마지막 요소의 위치: 마지막 노드는 항상 trailer의 이전 노드임

	def last(self):
		"""Return the last Position in the list (or None if list is empty)."""
		return self._make_position(self._trailer._prev)

 

6) 위치 p의 이전 위치

• 위치가 유효한지 확인
• 위치가 가리키는 노드를 구함 (self._validate()를 통해 노드의 레퍼런스를 구함)
• 노드의 이전 노드의 위치를 반환

	def before(self, p):
		"""Return the Position just before Position p (or None if p is first)."""
		node = self._validate(p)
		return self._make_position(node._prev)

 

7) 위치 p의 다음 위치

• 위치가 유효한지 확인
• 위치가 가리키는 노드를 구함 (self._validate()를 통해 노드의 레퍼런스를 구함)
• 노드의 다음 노드의 위치를 반환

	def after(self, p):
		"""Return the Position just after Position p (or None if p is last)."""
		node = self._validate(p)
		return self._make_position(node._next)

 

8) generator 정의

• __iter__()을 구현하여 generator로 정의
• 첫번째 노드부터 시작하여 마지막 노드까지 이동하면서 노드가 가리키는 요소를 반환

	def __iter__(self):
		"""Generate a forward iteration of the elements of the list."""
		cursor = self.first()
		while cursor is not None:
			yield cursor.element()
			cursor = self.after(cursor)

 

9) 두 위치 사이에 새로운 요소 삽입

• _DoublyLinkedBase의 _insert_between()함수를 오버라이드
• 두 노드 사이에 새로운 노드를 생성하여 삽입한 후 위치 반환

	def _insert_between(self, e, predecssor, successor):
		"""Add element between existing nodes and return new Position."""
		node = super()._insert_between(e, predecessor, successor)
		return self._make_position(node)

 

10) 처음 노드로 삽입: header와 header의 다음 노드 사이에 새로운 노드를 삽입하고 위치 반환

	def add_first(self, e):
		"""Insert element e at the front of the list and return new Position."""
		return self._insert_between(e, self._header, self._header._next)

 

11) 마지막 노드로 삽입: trailer와 trailer 이전 노드 사이에 새로운 노드를 삽입하고 위치를 반환

	def add_last(self, e):
		"""Insert element e at the back of the list and return new Position."""
		return self._insert_between(e, self._trailer._prev, self._trailer)

 

12) 위치 p의 앞에 삽입

• 지정된 위치가 유효한지 확인하고 노드를 반환받음
• 노드 앞에 새로운 노드를 삽입하고 위치를 반환

	def add_before(self, p, e):
		"""Insert element e into list before Position p and return new Position."""
		original = self._validate(p)
		return self._insert_between(e, original._prev, original)

 

13) 위치 p의 뒤에 삽입

• 지정된 위치가 유효한지 확인하고 노드를 반환받음
• 노드 뒤에 새로운 노드를 삽입하고 위치를 반환

	def add_after(self, p, e):
		"""Insert element e into list after Position p and return new Position."""
		original = self._validate(p)
		return self._insert_between(e, original, original._next)

 

14) 위치 p의 노드 삭제

• 지정된 위치가 유효한지 확인하고 노드를 반환받음
• 노드를 삭제

	def delete(self, p):
		"""Remove and return the element at Position p."""
		original = self._validate(p)
		return self._delete_node(original)			# inherited method returns element

 

15) 위치 p의 값을 대체

• 지정된 위치가 유효한지 확인하고 노드를 반환받음
• 노드의 요소를 변경하고 이전 노드 값을 반환

	def replace(self, p, e):
		"""Replace the element at Position p with e.
        Return the element formerly at Position p."""
		original = self._validate(p)
		old_value = original._element				# temporarily store old element
		original._element = e				 	# replace with new element
		return old_value

 

6. 성능 분석

양방향 연결 리스트로 포지션 리스트를 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다.

Operation	Running Time	Dynamic Array와의 비교
L.first()	O(1)	O(1)
L.last()	O(1)	O(1)
L.before(p)	O(1)	O(1)
L.after(p)	O(1)	O(1)
L.is_empty()	O(1)	O(1)
len(L)	O(1)	O(1)
iter(L)	O(n)	O(n)
L.add_last(e)	O(1)	O(1)	data.append(value)
L.replace(p, e)	O(1)	O(1)

Operation	Running Time	Dynamic Array와의 비교(amortized)
L.add_first(e)	O(1)	O(n)	data.insert(k, value)
L.add_before(p, e)	O(1)	O(n)	data.insert(k, value)
L.add_after(p, e)	O(1)	O(n)	data.insert(k, value)
L.delete(p)	O(1)	O(n)	data.pop(k)

다음 게시글에선 포지션 리스트로 삽입 정렬을 구현한 후, 연결 리스트를 마칠 것이다.