[자료구조] Single Linked List (단순 연결 리스트) 구현

Single Linked List (단순 연결 리스트)

파이썬으로 구현 해 보았다.

# Single Linked List

class Node:
    def __init__(self, item, next=None):
        self.item = item
        self.next = next


class SingleLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def list_size(self):
        return self.size

    def is_empty(self):
        if self.size != 0:
            return False
        else:
            return True

    def select_node(self, idx):
        if idx >= self.size:
            print("Index Error")
            return None
        if idx == 0:
            return self.head
        else:
            target = self.head
            for cur in range(idx):
                target = target.next
            return target

    def insert_first(self, item):
        if self.is_empty():
            self.head = Node(item)
        else:
            self.head = Node(item, self.head)
        self.size += 1

    def insert(self, item, idx):
        if self.is_empty():
            self.head = Node(item)
            self.size += 1
        elif idx == 0:
            self.insert_first(self, item)
        else:
            target = self.select_node(idx - 1)
            if target == None:
                return
            new_node = Node(item)
            tmp = target.next
            target.next = new_node
            new_node.next = tmp
            self.size += 1

    def delete(self, idx):
        if self.is_empty():
            print('Underflow: Empty Linked List Error')
            return
        elif idx >= self.size:
            print('Overflow: Index Error')
            return
        elif idx == 0:
            target = self.head
            self.head = target.next
            del(target)
            self.size -= 1
        else:
            pretarget = self.select_node(idx - 1)
            deltarget = pretarget.next
            pretarget.next = deltarget.next
            del(deltarget)
            self.size -= 1

    def print_list(self):
        target = self.head
        while target:
            if target.next != None:
                print(target.item, '-> ', end='')
                target = target.next
            else:
                print(target.item)
                target = target.next


single_linked_list = SingleLinkedList()

print('<insert>')
for i in range(5):
    single_linked_list.insert_first(i)
single_linked_list.print_list()
print('size : ', single_linked_list.list_size())
print()

print('<delete>')
for i in range(5):
    single_linked_list.delete(0)
    single_linked_list.print_list()
print('size : ', single_linked_list.list_size())


"""
<결과>
<insert>
4 -> 3 -> 2 -> 1 -> 0
size :  5

<delete>
3 -> 2 -> 1 -> 0
2 -> 1 -> 0
1 -> 0
0
size :  0
"""

파이썬으로 자료구조 공부를 하진 않았으나, C, C++와 Java를 알고있어서 self와 같은 개념이 별로 어렵게 다가오진 않았다.

self는 Java의 this와 비슷하다고 보면 된다.
Java에선 메소드의 파라미터에 this를 표기하진 않지만 Python에선 메소드의 첫번째 파라미터에 명시하여 사용한다. (self가 아닌 다른 이름도 사용해도 되지만 암묵적으로 이렇게 표기한다.)

 

참고자료

• 공대생의 차고