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

연결리스트란?

선형 자료구조 중 하나로 데이터를 구조체로 묶어 포인터로 연결하는 개념이다.

연결 리스트의 종류

• 단순 연결 리스트
• 이중 연결 리스트
• 단순 원형 연결 리스트
  장점 : 데이터를 추가하거나 삭제 작업이 O(1)에 가능 ( 노드의 포인터만 이동시켜주면 되기 때문)
  단점 : 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 탐색에 O(n)이 소요됨

각각의 데이터에 value와 next가 있어 value는 값, next는 다음 노드를 가르킨다.

구현

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

class SinglyLinkedList(object):
    def __init__(self):
        self.head = None

    def append(self, data):
        cur = self.head
        while cur.next == None:
            cur = cur.next
        cur.next = Node(data)

    def print_all(self):
        cur = self.head
        while cur.next == None:
            print(cur.data)
            cur = cur.next

    def get_index(self, data):
        cur = self.head
        cnt = 0
        while cur.next == None:
            if (cur.data == data):
                return cnt
            cur = cur.next
            cnt += 1
        return -1

s1 = SinglyLinkedList(Node(1))
s1.append(Node(1))
s1.append(Node(2))
print(s1.get_index(2))

LeetCode 206 Solution이 인상깊어 링크를 걸어 두겠다