Positon ADT

Position ADT는 데이터구조에서 객체의 위치를 추상화한 것이다.
배열의 셀 혹은 연결리스트의 노드 등 다양한 데이터를 저장 가능하다.

Node List ADT

Node List ADT는 데이터 구조에서 임의의 객체를 저장하는 위치(Position)들의 시퀀스(sequence)를 모델링한 추상 데이터 타입이다. 각 위치는 하나의 객체를 저장하며, 리스트 내에서 이전 위치와 다음 위치를 가리키는 포인터(주소)를 사용하여 서로 연결된다.
Node List ADT는 리스트의 맨 앞이나 맨 뒤에 객체를 삽입하거나 삭제하는 기본적인 연산들을 제공한다. 또한, 리스트의 각 위치(Position)를 조회하고 수정할 수 있는 추상 연산들도 제공한다.
Node List ADT는 리스트, 큐, 스택 등과 같은 데이터 구조에서 널리 사용된다.

Positional Accessor Operations

first(): List의 맨 앞 요소를 반환한다. List가 비어있다면 None을 반환한다.

last(): List의 맨 뒤 요소를 반환한다. List가 비어있다면 None을 반환한다.

before(P): P 위치 이전 요소를 반환한다. P가 첫 번째 위치라면 None을 반환한다.

after(P): P 위치 이후 요소를 반환한다. P가 마지막 위치라면 None을 반환한다.

is_empty(): List가 비어있다면 True를 반환한다.

len(L): List의 element 수를 반환한다.

iter(L): List의 요소들을 순차적으로 반환한다.

add_first(e): List의 앞 쪽에 새 element를 삽입한 후 위치를 반환한다.

add_last(e): List의 뒤 쪽에 새 element를 삽입한 후 위치를 반환한다.

add_before(p, e): 새 element를 p의 앞에 삽입한 후 위치를 반환한다.

add_after(p, e): 새 element를 p의 뒤에 삽입한 후 위치를 반환한다.

replace(p, e): p와 e의 위치를 바꾼 후 위치 p에 저장된 이전 노드를 반환한다.

delete(p): p 요소를 제거한 후 반환한다.

구현코드

from DoublyLinkedList import DoublyLinkedList

class PositionalList(DoublyLinkedList):
    
    class Position:
        
        def __init__(self):
            self.container = None
            self.node = None
            
        def element(self):
            return self.node.element
        
        def __eq__(self, other):
            return type(other) is type(self) and other.node is self.node
        
        def __ne__(self, other):
            return not(self == other)
        
    
    def validate(self, p):
        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:
            raise ValueError('p is no longer valid')
        return p.node
    
    def make_position(self, node):
        if node is self.header or node is self.trailer:
            return None
        else:
            return self.Position(self, None)
        
    def first(self):
        return self.make_position(self.header.next)
    
    def last(self):
        return self.make_position(self.trailer.prev)
    
    def before(self, p):
        node = self.validate(p)
        return self.make_position(node.prev)
    
    def __iter__(self):
        cursor = self.first()
        while cursor is not None:
            yield cursor.element()
            cursor = self.after(cursor)
    
    def insert_between(self, e, predecessor, succesor):
        node = super().insert_between(e, predecessor, succesor)
        return self.make_position(node)
    
    def add_first(self, e):
        return self.insert_between(e, self.header, self.header.next)
    
    def add_last(self, e):
        return self.insert_between(e, self.trailer.prev, self.trailer)
    
    def add_before(self, p, e):
        original = self.validate(p)
        return self.insert_between(e, original.prev, original)
    
    def add_after(self, p, e):
        original = self.validate(p)
        return self.insert_between(e, original, original.next)
    
    def delete(self, p):
        original = self.validate(p)
        return self.delete_node(p)
    
    def replace(self, p, e):
        original = self.validate(p)
        old_value =original.element
        original.element = e
        return old_value