[Python] 싱글 링크드 리스트 (단순 연결 리스트)

아마 자료구조를 공부하면 처음 구현하게 될 싱글 링크드 리스트.

워낙 자료도 방대하고 기구현된 소스코드가 많지만,

그만큼 기초는 중요하기에 직접 구현하면서 지식을 익혀보는 것이 낫다.

 

개인적인 생각이지만,

아주 기초적인 노드의 활용 방식을 몸소 익힐 수 있다는 점만으로도 단순 연결 리스트의 구현은 해볼 가치가 있다고 생각한다.

 

---

기초적인 지식

 

1. 시간복잡도

Single Linked List
	최선	최악
삽입	O(1)	O(1)
삭제	O(1)	O(1)
탐색	O(k)	O(N)

※ 단, 함정 있음. (아래 단점 항목 참고)

 

2. 장점

• 삽입과 삭제가 O(1)에 이루어진다.
• 삽입과 삭제를 할 때마다 동적으로 링크드 리스트의 크기가 결정되므로 전통적인 배열(Array)에 비해 처음부터 큰 공간을 할당할 필요가 없어진다.
• 메모리 관리가 용이하다. (사실상 이게 가장 큰 이유이다.)

3. 단점

• Random Access, 즉 배열처럼 index를 통해 탐색이 불가능하다.
• 탐색이 O(N)이 걸린다. (Head부터 Tail까지 모두 탐색 시)
• 사실상 삽입과 삭제가 왼쪽에서(Head에서) 이루어지지 않을 경우, 결국 탐색을 먼저 해야 하기 때문에 삽입과 삭제 모두 적게는 O(k)부터 최악의 경우 O(N)까지 걸릴 가능성이 있다. 이게 뭔 개소리야
• 파이썬에서 링크드 리스트는 의미가 크게 없는 게, 그냥 리스트 쓰면 된다. C++의 STL vector보다도 훨씬 쓰기 간편하며, 어떠한 타입의 데이터도(심지어 튜플이나 리스트마저) 넣을 수 있고 동적으로 메모리 관리가 되기 때문에, 링크드 리스트의 의미가 크게 퇴색된다.

4. 결론

• 파이썬의 리스트를 사용하자.
• ……

 

---

링크드 리스트의 구조도

 

링크드 리스트의 구조도

반응형

---

소스 코드

#Single Linked List

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

class SList(object):
    def __init__(self):
        self.head = Node(None)
        self.size = 0
        
    def listSize(self):
        return self.size
    
    def is_empty(self):
        if self.size != 0:
            return False
        else:
            return True
        
    def selectNode(self, idx):
        if idx >= self.size:
            print("Index Error")
            return None
        if idx == 0:
            return self.head
        else:
            target = self.head
            for cnt in range(idx):
                target = target.next
            return target
        
    def appendleft(self, value):
        if self.is_empty():
            self.head = Node(value)
        else:
            self.head = Node(value, self.head)
        self.size += 1
    
    def append(self, value):
        if self.is_empty():
            self.head = Node(value)
            self.size += 1
        else:
            target = self.head
            while target.next != None:
                target = target.next
            newtail = Node(value)
            target.next = newtail
            self.size += 1
        
    def insert(self, value, idx):
        if self.is_empty():
            self.head = Node(value)
            self.size += 1
        elif idx == 0:
            self.head = Node(value, self.head)
            self.size += 1
        else:
            target = self.selectNode(idx-1)
            if target == None:
                return
            newNode = Node(value)
            tmp = target.next
            target.next = newNode
            newNode.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:
            target = self.selectNode(idx-1)
            deltarget = target.next
            target.next = target.next.next
            del(deltarget)
            self.size -= 1
            
    def printlist(self):
        target = self.head
        while target:
            if target.next != None:
                print(target.data, '-> ', end='')
                target = target.next
            else:
                print(target.data)
                target = target.next

이게 기본 소스 코드이다.

 

SList는 Single Linked List의 클래스이다.

보통 블로그를 보다 보면 처음 학습할 때 헷갈리는 것이,

누군가는 Node 클래스를 Single Linked List 클래스 안에 넣고,

누군가는 밖에 넣는다는 것이다. (위의 소스 코드처럼)

 

두 방식의 차이점은 크게 없다.

다만 Single Linked List 클래스 안에 Node 클래스가 있는 경우,

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

위의 소스 코드에서 아래의 소스 코드처럼 바꾸면 된다.

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

이렇게.

 

앞으로도 트리 자료구조나 그래프, Trie 등 여러 자료구조를 짜면서 Node 클래스를 매번 짜야할 텐데,

필자는 처음 배울 때 Node 클래스를 밖에 정의하는 것으로 배워서 쭉 이렇게 짠다.

이건 처음 프로그램을 배울 때는 크게 차이가 없고, 그저 방식의 차이만이 있는 것이라고 생각한다.

 

소스 코드 자체가 어렵지는 않으나,

포인터의 개념이 없거나 클래스의 개념이 미약하면 굉장히 어려워보일 수는 있다.

 

특히 self나 target.next, self.head 같은 것.

이럴 때는 크게 걱정하지 말고, 소스 코드가 아니라 영어 지문을 읽는다고 생각하면 한결 쉬워진다.

 

가령, 다음과 같은 소스 코드에서,

    def append(self, value):
        if self.is_empty():
            self.head = Node(value)
            self.size += 1
        else:
            target = self.head
            while target.next != None:
                target = target.next
            newtail = Node(value)
            target.next = newtail
            self.size += 1

else문 다음부터 읽어보자.

우선 타겟으로 하는 목표 노드를 target이라는 변수(파이썬에서는 변수 객체)에 집어 넣기 위해,

탐색을 해야 하기 때문에 head부터 target에 넣어준다.

이때 head는 SList라는 클래스의, 그러니까 myself, himself처럼 class<self>에 저장되어 있는 head를 불러온다.

 

그리고 target.next, 그러니까 target의 다음 번 노드가 None(파이썬의 Null 객체)이 아닐 때까지,

target에 target.next를 대입하며 탐색해간다.

만약 target.next가 None이 되며 링크드 리스트의 마지막 노드에 도달하면, 탐색을 멈춘다.

 

그리고 newtail이라는 변수에 입력받은 value 값을 갖고 있는 새로운 Node를 생성하여 대입해준다.

마지막으로, 아까 탐색한 링크드 리스트의 마지막 노드의 next를 newtail에 집어넣었던 Node와 연결시켜주면 된다.

 

이 소스 코드를,

mylist = SList()
mylist.append('A')
mylist.printlist()
mylist.append('B')
mylist.printlist()
mylist.append('C')
mylist.printlist()
mylist.insert('D', 1)
mylist.printlist()
mylist.appendleft('E')
mylist.printlist()
print(mylist.listSize())
mylist.delete(0)
mylist.printlist()
mylist.delete(3)
mylist.printlist()
mylist.delete(0)
mylist.printlist()
mylist.appendleft('A')
mylist.printlist()

위와 같이 실행해보면,

A
A -> B
A -> B -> C
A -> D -> B -> C
E -> A -> D -> B -> C
5
A -> D -> B -> C
A -> D -> B
D -> B
A -> D -> B

결과가 이렇게 나온다.

 

싱글 링크드 리스트에서 배운 노드 개념이 나중에도 자주 사용되니,

꼭 익혀두도록 하자.