Python으로 구현하는 자료구조 : Linked List (1) Singly linked list

Linked list(연결 리스트)는 (데이터와 다음 노드의 주소를 담고 있는) 노드들이 

한 줄로 연결되어 있는 방식의 자료 구조입니다.

연결되는 방향에 따라, (1) Singly linked list (단일 연결 리스트), (2) Doubly linked list (이중 연결 리스트), (3) Circular linked list (환형 연결 리스트)가 있습니다. 

이 포스팅에서는 Linked list와 Singly Linked list 의 특징을 알아보고

파이썬으로 Singly Linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다.

---

# Linked list란?

Linked List는 데이터를 노드의 형태로 저장합니다. 노드에는 데이터와 다음 노드를 가르키는 포인터를 담은 구조로 이루어져 있습니다.

node의 모습

Linked list는 Array 처럼 선형 데이터 자료구조이지만, Array는 물리적인 배치 구조 자체가 연속적으로 저장되어 있고 Linked list는 위의 노드의 Next 부분에 다음 노드의 위치를 저장함으로써 선형적인 데이터 자료구조를 가집니다.

Python 내장 함수의 시간 복잡도에서 List의 삽입과 삭제의 시간복잡도가 O(n)이 걸리는 것은 배열이 물리적인 데이터의 저장 위치가 연속적이어야 하므로 데이터를 옮기는 연산작업이 필요하기 때문입니다. 하지만 Linked List는 데이터를 삽입, 삭제할 경우, 노드의 Next 부분에 저장한 다음 노드의 포인터만 변경해주면 되므로 배열과 비교하였을 때 linked list가 효율적으로 데이터를 삽입, 삭제할 수 있습니다. 그러나 이러한 안타깝게도 Linked List에서 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작하여야 합니다. 그 시간이 O(n) 만큼 걸리게 되므로 탐색에 있어서는 배열이나 트리 구조에 비해 상대적으로 느리다고 할 수 있습니다.

# Linked list의 장점과 단점은요

Linked lsit의 장점은,
(1) Linked list의 길이를 동적으로 조절 가능
(2) 데이터의 삽입과 삭제가 쉬움

Linked list의 단점은,
1) 임의의 노드에 바로 접근할 수 가 없음
(2) 다음 노드의 위치를 저장하기 위한 추가 공간이 필요함
(3) Cache locality를 활용해 근접 데이터를 사전에 캐시에 저장하기가 어려움
(4) Linked list를 거꾸로 탐색하기가 어려움

※ cache locality : 대부분 프로그램은 한번 사용한 데이터를 다시 사용할 가능성이 높고, 그 주변의 데이터도 곧 사용할 가능성이 높은 데이터 지역성을 가지고 있습니다. 데이터 지역성을 활용하여 메인 메모리에 있는 데이터를 캐시 메모리에 불러와 두고, CPU가 필요한 데이터를 캐시에서 먼저 찾도록 하면 시스템 성능을 향상시킬 수 있습니다.

# 단일 연결 리스트 구현하기

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간(다음 노드의 주소를 담는 공간)이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다.

# 삽입

# 삭제

# 파이썬 코드

# Node 클래스 선언
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
# Singly linked list 클래스 선언
class SinglyLinkedList(object):
    def __init__(self):
        self.head = None
        self.count = 0
 
    # Add new node at the end of the linked list
    def append(self, node):
        if self.head == None:
            self.head = node
        else:
            cur = self.head
            while cur.next != None:
                cur = cur.next
            cur.next = node
 
    # return first index of data in the linked list
    def getdataIndex(self, data):
        curn = self.head
        idx = 0
        while curn:
            if curn.data == data:
                return idx
            curn = curn.next
            idx += 1
        return -1
 
    # Add new node at the given index
    def insertNodeAtIndex(self, idx, node):
        """
        A node can be added in three ways
        1) At the front of the linked list
        2) At a given index.
        3) At the end of the linked list.
        """
        curn = self.head
        prevn = None
        cur_i = 0
 
        # (1) Add 0 index
        if idx == 0:
            if self.head:
                nextn = self.head
                self.head = node
                self.head.next = nextn
            else:
                self.head = node
        else:
            # (2) Add at given index &
            # (3) At the end of the linked list
            while cur_i < idx:
                if curn:
                    prevn = curn
                    curn = curn.next
                else:
                    break
                cur_i += 1
            if cur_i == idx:
                node.next = curn
                prevn.next = node
            else:
                return -1
 
    # Add new node before the given data
    def insertNodeAtData(self, data, node):
        index = self.getdataIndex(data)
        if 0 <= index:
            self.insertNodeAtIndex(index, node)
        else:
            return -1
 
    # Delete data at given index.
    def deleteAtIndex(self, idx):
        curn_i = 0
        curn = self.head
        prevn = None
        nextn = self.head.next
        if idx == 0:
            self.head = nextn
        else:
            while curn_i < idx:
                if curn.next:
                    prevn = curn
                    curn = nextn
                    nextn = nextn.next
                else:
                    break
                curn_i += 1
            if curn_i == idx:
                prevn.next = nextn
            else:
                return -1
 
    # Empty linked list
    def clear(self):
        self.head = None
 
    # 출력
    def print(self):
        curn = self.head
        string = ""
        while curn:
            string += str(curn.data)
            if curn.next:
                string += "->"
            curn = curn.next
        print(string)
 
 
if __name__ == "__main__":
    sl = SinglyLinkedList()
    sl.append(Node(1))
    sl.append(Node(2))
    sl.append(Node(3))
    sl.append(Node(5))
    sl.insertNodeAtIndex(3, Node(4))
    sl.print()
    print(sl.getdataIndex(1))
    print(sl.getdataIndex(2))
    print(sl.getdataIndex(3))
    print(sl.getdataIndex(4))
    print(sl.getdataIndex(5))
    sl.insertNodeAtData(1, Node(0))
    sl.print()