[CLRS] [10-1] Linked List(연결리스트)

0. Intro

- 자료구조에서 꼭 알아야하는 연결리스트에 대해 알아보자.

- 해당 게시글에서는 단방향 연결리스트만 서술하고자 한다.

1. 리스트

- 리스트(list | 파이썬 내장 리스트와 다름)는 순서가 있는 데이터를 나열한 자료구조

- 실생활 예) 학생 명단, 상점의 판매 품목, 실시간 급상승 검색어...

 

2. 노드

- 연결리스트를 구성하는 각각의 원소

- 데이터와 포인터(reference)를 가진다.

 

2.1. 노드 클래스 구현

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

 

#ex 1

n0 = Node('A')
n1 = Node('B')
n2 = Node('C')

n0.next = n1 # n0 뒤에 n1을 연결함
n1.next = n2 # n1 뒤에 n2를 연결함

print(n0.data)
print(n0.next.data)
print(n0.next.next.data)

----------------------------------------

A
B
C

#ex 2

n2 = Node('C')
n1 = Node('B',n2)
n0 = Node('A',n1)

print(n0.data)
print(n0.next.data)
print(n0.next.next.data)


_______________________________________________________________



A
B
C

 

3. 연결리스트(linked list)

- 리스트를 구현하는 방법중 하나

- 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조

3.1. 머리노드(head node)

- 연결리스트의 맨 앞에 있는 노드

3.2.꼬리노드(tail node)

- 연결리스트의 맨 끝에 있는 노드 

 

4. 연결리스트 구현

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

    def __len__(self):
        return self.no

4.1. add_first() 메소드 구현

    def add_first(self,data):
        ptr = self.head
        self.head = Node(data,ptr)
        self.no += 1

4.2. add_last() 메소드 구현

    def add_last(self,data):
        if self.head is None:
            self.add_first(data)
        else:
            ptr = self.head
            if ptr.next:
                ptr= ptr.next
            ptr.next = Node(data,ptr)
            self.no += 1

 

4.3. print() 메소드 구현

    def print(self):
        ptr = self.head
        while ptr:
            print(ptr.data, end='')
            if ptr.next:
                print('->',end ='')
            else:
                print()
            ptr = ptr.next

4.4. search() 메소드 구현

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

 

    def __contains__(self,data):
        return self.search(data) >= 0

 

4.5. remove_first() 메소드 구현

    def remove_first(self):
        if self.head:
            self.head = self.head.next
            self.no -= 1

 

4.6. remove_last() 메소드 구현

    def remove_last(self):
        if self.head:
            if self.head.next is None:
                self.remove_first()
            else:
                ptr = self.head
                pre = self.head

                while ptr.next:
                    pre = ptr
                    ptr = ptr.next

                pre.next = None
                self.no -= 1

4.7. clear() 메소드 구현

    def clear(self):
        while self.head:
            self.remove_first()
        self.no = 0