연결 리스트 (Linked List)

Linked List란?

값 + 다음 노드에 대한 포인터(참조)가 포함된 노드로 이루어진 선형 리스트

마지막 노드는 null 값(파이썬은 None)을 갖음

 

class Node(object):
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer

    def getData(self):
        return self.value

    def getNext(self):
        return self.pointer

    def setData(self, newdata):
        self.value = newdata

    def setNext(self, newpointer):
        self.pointer = newpointer


if __name__ == "__main__":
    L = Node("a", Node("b", Node("c", Node("d"))))
    assert(L.pointer.pointer.value == "c")

    print(L.getData())
    print(L.getNext().getData())
    print(L.getNext().getNext().getData())
    L.setData("aa")
    L.setNext(Node("e"))
    print(L.getData())
    print(L.getNext().getData())

Linked List 형식

Linked List 쓰는 이유

연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖음

[배열은 O(n)의 복잡도를 갖음]

BUT, 추가와 삭제 속도가 빠른 대신에 연결리스트의 각 노드는 인덱스를 갖지 않음

→ 특정 데이터를 검색할 때 O(n)의 시간 복잡도를 갖음

정리

탐색과 정렬을 자주 한다면 배열 리스트 사용!

추가와 삭제가 많다면 연결 리스트 사용!