Singly Linked List

Singly Linked List

싱글 링크드 리스트는 선형구조 형태인 노드들의 집합입니다. 각 노드는 시퀀스의 요소인 객체에 대한 참조를 저장합니다. 자신의 다음 노드를 참조( next )합니다.

<노드>

싱글 링크드 리스트의 첫번째와 마지막 노드는 head 와 tail 입니다. head 먼저 시작해서 각 노드에 참조에 따라 다른 노드로 이동하면서 최종적으로 tail노드에 도달할 수 있습니다. 일반적으로 이 프로세스를 Linked List traversing 이라고 합니다. 노드의 next 참조가 다른 노드에 대한 링크 또는 포인터 로 보여질 수 있기 떄문에, 리스트 traversing 처리는 link hopping 또는 pointer hopping 이라고 합니다.

싱글 링크드 리스트 헤드 요소 삽입

싱글 링크드 리스트의 중요한 프로퍼티는 길이가 정해져 있지 않다는 것 입니다. 싱글 링크드 리스트를 사용할 때, 쉽게 헤드에 요소를 삽입 할 수 있습니다.
메인 아이디어는 노드를 만들고, 노드에 새 요소를 세팅합니다. 그리고 새 노드에 next 링크에 head 노드를 참조하도록 한 후 헤드가 새 노드를 가리킵니다.

<싱글 링크드 리스트 헤드 요소 삽입>

"""python pseudo code"""
def add_first(L,e):
    newest = Node(e)
    newest.next = L.head
    L.head = newest
    L.size +=1

싱글 링크드 리스트 테일 요소 삽입

테일에 요소 삽입도 쉽겍 할 수 있습니다. 먼저 노드를 생성하고 새 요소를 세팅합니다. 그리고 tail 삽입이기 때문에 next 는 None을 참조합니다. 테일 노드의 next는 새 노드를 가리키고 tail 은 새 노드를 가리킵니다.

<싱글 링크드 리스트 테일 요소 삽입>

"""python pseudo code"""
def add_last(L,e):
    newest = Node(e)
    newest.next = None
    L.tail.next = newest
    L.tail = newest
    L.size +=1

싱글 링크드 리스트로 스택 구현

class LinkedStack:
    """ 싱글 링크드 리스트로 LIFO 스택 구현 """

    class _Node:
        """ 가볍고, 논퍼블릭한 클래스 노드 """
        __slots__ = '_element', '_next'

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

    def __init__(self):
    """ 빈 스택 생성 """
        self._head = None
        self._size = 0

    def __len__(self):
    """ 스택의 요소들의 수를 리턴 """
        return self._size

    def is_empty(self):
        return self._size == 0

    def push(self, e):
    """ 스택의 탑에 요소를 추가 """
        self._head = self._Node(e, self._head)
        self._size =1

    def top(self):
    """ 스택의 탑을 리턴 (삭제 x) """

        if self.is_empty():
            raise Empty('Stack is empty')
        else:
            return self._head._elemen t

    def pop(self):
    """ 마지막 요소를 제거하고 그 값을 리턴 """

        if self.is_empty():
            raise Empty('Stack is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -=1
        return answer

각 메서드 시간 복잡도

Operation	Running Time
S.push(e)	O (1)
S.pop()	O (1)
S.top()	O (1)
len(s)	O (1)
S.is_empty	O (1)

싱글 링크드 리스트로 큐 구현

class LinkedQueue:
    """ 싱글 링크드 리스트를 이용해서 FIFO 큐 구현 """

    class _Node:
        """ 가볍고, 논퍼블릭한 클래스 노드 """
        __slots__ = '_element', '_next'

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

    def __init__(self):
        """ 빈 큐 생성 """
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self):
    """ 쿠의 길이를 리턴 """
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
    """ 큐의 앞 요소를 리턴 (삭제 x) """

    if self.is_empty():
        raise Empty('Queue is empty')
    return self._head._element

    def dequeue(self):

    """ 앞 요소를 제거하고 리턴 """

        if self.is_empty():
            raise Empty('Queue is empty')

        answer = self._head._element
        self._head = self._head._next
        self.size -= 1
        if self.is_empty():
            self.tail = None
        return answer

    def enqueue(self, e):
    """ 큐 마지막에 요소를 추가 """

        newest = self._Node(e,None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size -= 1

싱글 링크드 리스트로 원형 큐 구현

class CircularQueue:
    """ 싱글 링크드 리스트를 이용해서 FIFO 원형 큐 구현 """

    class _Node:
        """ 가볍고, 논퍼블릭한 클래스 노드 """
        __slots__ = '_element', '_next'

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

    def __init__(self):
        """ 빈 큐 생성 """
        self._tail = None
        self._size = 0

    def __len__(self):
    """ 쿠의 길이를 리턴 """
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
    """ 큐의 앞 요소를 리턴 (삭제 x) """

    if self.is_empty():
        raise Empty('Queue is empty')
    head = self._tail._next
    return head._element

    def dequeue(self):

    """ 앞 요소를 제거하고 리턴 """

        if self.is_empty():
            raise Empty('Queue is empty')

        oldhead = self._tail._next
        if self._size == 1:
            self._tail = None
        else:
            self._tail.next = oldhead._next
        self._size -=1
        return oldhead._element

    def enqueue(self, e):
    """ 큐 마지막에 요소를 추가 """
        newest = self._Node(e,None)
        if self.is_empty():
            newest._next = newest
        else:
            newest._next = self._tail._next
            self._tail._next = newest
        self._tail = newest
        self._size +=1

    def rotate(self):

    if self._size > 0:
        self._tail = self._tail._next