[자료구조] Singly Linked List(한 방향 연결리스트) class 구현 (python)

[자료구조] Singly Linked List(한 방향 연결리스트) class 구현

 

 

살펴볼 주요 개념:

- 한 방향 연결리스트의 클래스 구성(Node, SinglyLinkedList)

- 클래스 내부 메소드

한 방향 연결리스트를 파이썬으로 구현하기 위해서는 두 개의 클래스가 필요하다.

노드 클래스를 통해 각 노드를 정의하여 링크로 잇고, 이어진 리스트를 연산에 활용하는 singlyLinkedList 클래스가 필요하다.

아래에서는 두 가지 클래스를 구현해보도록 한다.

 

1. 한 방향 연결리스트의 클래스(node)

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

    def __str__(self):
        return str(self.key) # print(v)를 대신하는 함수

한 방향 연결리스트에는 key값과 다음 값을 가리키는 링크가 필요하다.

여기에서 다음 노드를 가리키는 것은 next이다. 모든 노드는 기본 값으로 next를 None으로 갖는다.

def __str__은 key를 print하는 함수인데, 없어도 무방하다.

a = Node(3)
b = Node(9)
c = Node(-1)

a.next = b
b.next = c

print(a)
print(a.next)
print(c.next)


## print 결과
3
9
None

노드 클래스를 이용해서 a, b, c를 인스턴스화 하고, 각각 3, 9, -1이라는 키를 담았다.

a의 key값은 3, next값은 None이 되고, b의 key값은 9, next값은 None이 되고, c의 key값은 -1, next값은 None이 된다.

 

그 다음 a.next = b를 정의해줌으로써 a의 다음 노드는 b라고 정의할 수 있게 된다.

b.next = c도 마찬가지.

자동으로 c는 마지막 tail 노드가 된다.

 

아래에 프린트한 결과를 보면 print(a)로 결과값이 나오는 것을 볼 수 있는데, 이는 노드 클래스에서 __str__을 정의했기 때문이다. __str__을 정의하지 않았다면, a.key, a.next.key를 print()안에 집어넣어서 결과값을 도출할 수 있다.

 

이러한 과정들을 다음 클래스에서 활용하여 singly Linked List로 만든다.

노드 클래스만으로는 리스트를 만들었다고 할 수는 없다. 기본 기능만 들어가있는 클래스이기 때문이다.

 

2. 한 방향 연결리스트의 클래스(singly)

(1) init 정의

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

각종 연산을 하기 위해서는 head pointer가 필요하다. 그렇기 때문에 각각의 노드에 헤드 값을 None으로 초기화하여 부여한다.

여기에서는 size를 둠으로써 리스트 전체의 크기를 한 번에 알 수 있게 할 것이다.

 

(2) 삽입 1. pushFront (맨 앞에 삽입), pushBack(맨 뒤에 삽입)

 

*pushFront

def pushFront(self, key):
    new_node = Node(key)
    new_node.next = self.head
    self.head = new_node
    self.size += 1

pushFront는 맨 앞에 삽입하는 것이다.

맨 앞에 위치할 노드를 new_node라고 하고, Node로 만든다.

 

new_node를 헤드로 만들면 된다. 과정은 다음과 같다.

new_node의 next값으로는 자기 자신의 head값을 준다. -> 자기 자신의 head 값으로 new_node 자신을 준다. 

그런 다음 사이즈를 +1 하면 삽입이 완료된다.

 

 

* pushBack

def pushBack(self, key):
    new_node = Node(key)
    if len(self) == 0:
        self.head = new_node
        return
    else:
        tail = self.head
        while tail.next != None:
            tail = tail.next
        tail.next = new_node
        self.size += 1

pushBack의 경우 마지막 노드를 찾아야 한다.

new_node를 노드화 하고, 만약 전체 리스트의 길이가 0이면 자기 자신이 처음 들어간 것이기 때문에 자기 자신을 헤드노드로 만들고 메소드를 종료한다.

 

그것이 아니라면(리스트 안에 어떤 노드가 존재), tail이라는 변수에 자기 자신의 head값을 담고, while문을 통해 tail의 next가 None이 될 때 까지(마지막 원소는 next가 없기 때문) tail = tail.next 를 수행한다. 즉, tail이 그 다음 노드화 되는 것이다.

그렇게 해서 while문을 빠져 나오면, tail은 현재 리스트의 마지막 노드가 되어 있다. 그러면 tali의 next값으로 new_node를 부여해준다.

 

그런 다음 사이즈를 1 업 해주고 메소드를 종료한다.

 

 

(3) 삽입 2. insert_after_key(특정 노드 뒤 삽입), insert_befort_key(특정 노드 앞 삽입)

 

특정 노드 앞, 뒤에 한 방향 노드를 삽입할 수 있다.

    def insert_after_key(self, x, data): # x : 새 노드를 삽입하려는 항목, data : 새 노드의 값
        n = self.head
        while n is not None:
            if n.key == x:
                break
            n = n.next
        if n is None:
            print("data not in the list")
        else:
            new_node = Node(data)
            new_node.next = n.next
            n.next = new_node

x라는 기존 노드 뒤에 data(새 노드의 key값)을 추가하는 것이다.

 

    def insert_before_key(self, x, data):
        if self.head is None:
            print("List has no element")
            return

        if x == self.head.key:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
            return

        n = self.head
        while n.next is not None:
            if n.next.key == x:
                break
            n = n.next
        if n.next is None:
            print("key not in the list")
        else:
            new_node = Node(data)
            new_node.next = n.next
            n.next = new_node

x노드 전에 data가 삽입되게 된다.

 

 

(4) 삭제. popFront(맨 앞 노드 삭제), popBack(맨 뒤 노드 삭제)'

 

* popFront

맨 앞 노드를 삭제한다.

    def popFront(self): # 1. head 수정 -> 2. size 수정
        if len(self) == 0:
            print("리스트 내에 원소가 존재하지 않습니다.")
            return None
        else: # 하나 이상 노드 존재
            x = self.head
            key = x.key
            self.head = x.next
            self.size -= 1
            del x # 맨 앞 노드를 삭제
            return key # pop한 키를 반환(x값)

삭제의 경우 삽입의 반대와 같다. 리스트 내에 원소가 존재하지 않는 경우를 빼고, self.head를 x의 다음값으로 만들고, 기존의 self.head를 pop하는 것이다.

 

 

* popBack

맨 뒤 노드를 삭제한다.

    def popBack(self): # tail 노드 삭제
        if len(self) == 0:
            print("리스트 안에 원소가 존재하지 않습니다.")
        else:
            prev, tail = None, self.head
            while tail.next != None: # 앞에서부터 tail을 찾아줌
                prev = tail
                tail = tail.next
            if len(self) == 1:
                self.head = None
            else:
                prev.next = tail.next
            key = tail.key
            del tail
            self.size -= 1
            return key

마찬가지이다. 리스트 내에 원소가 존재하지 않는 경우를 뺀다.

그 다음 tail노드를 찾는 과정을 통해 tail을 찾고, 기존의 tail은 삭제, pop하고, 기존의 tail의 이전 노드를 마지막 노드화(next노드가 None 이도록) 하는 과정을 거치면 된다.

 

 

(5) 탐색, iterator

 

* search

    def search(self, key):
        # key값의 노드를 리턴, 없으면 None
        v = self.head
        while v != None:
            if v.key == key:
                return v
            v = v.next

 

 

* iterator

    def __iterator__(self):
        v = self.head
        while v != None:
            yield v  # 리턴 같은 역할
            v = v.next

이터레이터는 순차적으로 for loop처럼 쓸 수 있게 만들어주는 것이다. iterable 하게 만들어준다고 보면된다.