개념

종류

• Singly Linked List
• Doubly Linked LIst
• Circular Linked List

특징

• 길이를 동적으로 조절 가능
• 데이터의 삽입, 삭제가 쉬움
• 탐색이 오래걸림

Python으로 구현

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

위 블로그에 있는 코드이다. Python으로 Linked List를 이용할 일은 거의 없으니 Python 스타일을 공부하는 의미에서 작성해본다.

Singly Linked List

# Node 클래스 선언
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

# Singly linked list 클래스 선언

class SignlyLinkedList(object):
    def __init__(self):
        self.head = None
        self.count = 0

    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

    def getDataIndex(self, data):
        curn = self.head
        idx = 0
        while curn:
            if curn.data == data:
                return idx
            curn = curn.next
            idx += 1
        return -1

    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 giben 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):
        cur_i = 0
        curn = self.head
        prevn = None
        nextn = self.head.next
        if idx == 0:
            self.head = nextn
        else:
            while cur_i < idx:
                if curn:
                    prevn = curn
                    curn = nextn
                    nextn = nextn.next
                else:
                    break
                cur_i += 1
            if cur_i == idx:
                prevn.next = nextn
            else:
                return -1

    # Emtpy linked list
    def clear(self):
        self.head = None

    # print
    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 = SignlyLinkedList()

    sl.append(Node(1))
    sl.append(Node(2))
    sl.append(Node(3))
    sl.append(Node(5))

    sl.insertNodeAtIndex(3, Node(4))
    sl.print()

    sl.deleteAtIndex(0)
    sl.deleteAtIndex(1)

    sl.print()

Doubly Linked List