[파이썬 자료구조] 단일연결리스트(Singly Linked List) 설명 및 코드

단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조

동적 메모리 할당을 받아 노드(node)를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결시킴

연결리스트에서는 삽입/삭제 시 항목들의 이동이 필요 없음

연결리스트에서는 자료를 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색 (Sequential Search)을 해야함

단순연결리스트에서 head는 맨 처음 노드라고 생각하면 됩니다. head를 통해서 노드로 순차적으로 탐색

그럼 코드를 통해 확인해볼게요

class SList:
    class _Node: #노드에 관한 클래스입니다.
        def __init__(self, element, next=None): #노드의 생성자입니다. 
            self._element = element #노드의 element값입니다.
            self._next = next  #노드가 가르키는 값입니다.
 
        def element(self): #element를 반환하는 함수
            return self._element
 
        def next(self): #next값을 반환하는 함수
            return self._next
 
        def set_element(self, element): #element를 설정해줍니다.
            self._element = element
 
        def set_next(self, next): #next를 설정해줍니다. 다음 노드를 가르키게 하는 함수
            self._next = next
 
        def __str__(self): #string으로 출력하기 위한 함수
            return str(self._element)
 
        def __repr__(self): #string으로 출력하기 위한 함수
            return str(self)
 
    def __init__(self): #SSL의 생성자입니다.
        """Create a singly linked list that contains head and tail"""
        self._head = None
        self._tail = None
 
    def __len__(self): #리스트의 길이를 반환해주는 함수
        length = 0
        node = self._head
        while node:
            length += 1
            node = node._next
        return length
 
    def __str__(self): #string으로 출력하기위한 함수
        count = 0
        p = self._head
        elements = []
        while p:
           element.append(p.element())
            p = p._next
            count += 1
        element.append("None")
        return f"{count}:" + ' -> '.join(elements)
 
    def __repr__(self): #string으로 출력하기위한 함수
        return str(self)
 
    def is_empty(self): #리스트가 비어있다면 
        return self._head is None
 
    def head(self): #헤드를 반환하는 함수
        return self._head
 
    def tail(self): #테일을 반환하는 함수, 노드의 마지막부분입니다.
        return self._tail
 
    def search(self, element): #특정 element를 찾아서 그 노드를 반환하는 함수
        """Search an element in self by link hopping through next"""
        p = self._head
        while p:  # while p is an actual node
            if p._element == element:  # node p contains the element to find
                return p  # if found, returns its node
            p = p._next  # otherwise, link hopping is taken place
        return None  # not found so returns None
 
    def insert_first(self, element): #리스트의 맨 앞에 element를 삽입하는 함수
        if self.is_empty():  # 노드가 비어있다면?
            p = self._Node(element) #element값을 node로 만들어서
            self._head = self._tail = p  # 그 노드를 head이자 tail로 만들어줍니다. 1개짜리 리스트가 만들어지겠죠?
        else:  
            self._head = self._Node(element, self._head) #노드를 만들어서 head가 되게합니다.
        return self._head
 
    def delete_first(self): #첫 노드를 삭제하는 함수 
        if self.is_empty():  # 비어있다면 삭제가 불가능하죠
            return None
        elif self._head == self._tail:  # 노드가 하나라면 head와 tail을 None값으로 해주면됩니다.
            p = self._head
            self._head = self._tail = None
            return p
        else: #리스트 길이가 충분하다면 head의 next를 head로 변경해주면 됩니다.
            p = self._head
            self._head = self._head._next
            return p
 
    def insert_after(self, element, p): # p노드 뒤에 노드를 삽입하는 함수
        #assert p is not None  리스트가 비어있지않다는것을 보장
 
        p._next = self._Node(element, p._next)
        if p == self._tail:  # update tail info
            self._tail = p._next
        return p._next
 
    def delete_after(self, p): #뒤에 노드를 삭제하는 함수
        if p == self._tail:  
            return None
        q = p._next
        p._next = q._next
        if q == self._tail:
            self._tail = p
        return q
 
    def insert_last(self, element): #마지막에 노드를 삽입하는 함수
        if self.is_empty():  # 비어있다면 삭제가 불가능 합니다.
            p = self._Node(element)
            self._head = self._tail = p
            return p
 
        return self.insert_after(element, self._tail)
 
    def delete_last(self): #노드의 다음 노드를 삭제하는 함수
        if self.is_empty():
            return None
        elif self._head == self._tail:  # there is only one node in SLL
            p = self._head
            self._head = self._tail = None
            return p
        else:
            p = self._head
            while p._next:
                if p._next._next:
                    p = p._next
                else:  # p is the penultimate node
                    return self.delete_after(p)
            return None  # Never reach here
 
    def reverse_recursively(self, node): #리스트를 recursively하게 뒤집는 함수
        cur = node  
        next = cur._next
        if not next:
            self._head = cur
            return
        self.reverse_recursively(cur._next)
        next._next = cur
        cur._next = None
        self._tail = cur
 
    def reverse_iteratively(self, node):  #리스트를 iteratively하게 뒤집는 함수
        pre = None
        cur = node
        self._tail = node
        while cur is not None:
            next = cur._next
            cur._next = pre
            pre = cur
            cur = next
        self._head = pre
 
    def index(self, element): #index를 반환하는 함수
        p = self._head
        idx = 0
        while p:
            if p._element == element:
                return idx  # found returns its position
            p = p._next
            idx += 1
        raise IndexError  # not found
 
    def __iter__(self):
        self._pos = self._head
        return self
 
    def __next__(self):
        if self._pos is None:
            raise StopIteration
        else:
            element = self._pos._element
            self._pos = self._pos._next
            return element
 
    def __getitem__(self, idx):
        p = self._head
        while idx:
            p = p._next
            idx -= 1
        return p._element
 
    def __setitem__(self, idx, element):
        p = self._head
        while idx:
            p = p._next
            idx -= 1
        p._element = element

단일연결리스트의 여러 함수와 reverse하는 코드였습니다.