[자료구조]연결리스트(Linked List)

연결리스트

차례로 연결된 노드를 표현하는 자료구조
단방향, 양방향
단방향의 각 노드는 다음 노드를 가리킨다
양방향의 각 노드는 다음 노드와 이전 노드를 가리킨다

단방향 연결리스트 기본

 

구현

간단하게 연결리스트 구현
python

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

    def appendToTail(self, d):
        end = Node(d)
        while(self.next != None):
            self = self.next
        self.next = end

    def allGet(self):
        while(self.next != None):
            print(self.data)
            self = self.next
        print(self.data)


node = Node("0")

node.appendToTail("1")
node.appendToTail("2")
node.appendToTail("3")

node.allGet()

이 상태로도 간단하게 구현할 수 있다

하지만 연결리스트 head 가 없어서 어디를 가리키고 있는지 알 수가 없다

 

LinkedList 클래스를 만들어 head에 첫번째 Node를 초기화 시킨다

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


class LinkedList:
    def __init__(self):
        self.head = None

    def appendToTail(self, d):
        end = Node(d)
        if self.head is None:
            self.head = end
            return

        n = self.head
        while(n.next != None):
            n = n.next
        n.next = end

    def allGet(self):
        n = self.head
        while(n.next != None):
            print(n.data)
            n = n.next
        print(n.data)


linkedlist = LinkedList()

linkedlist.appendToTail("1")
linkedlist.appendToTail("2")
linkedlist.appendToTail("3")

linkedlist.allGet()