[OOP] Linked List 자료구조 만들기

Linked List란?

 

- Linked List란?

 

배열 -> 연결된 공간에 데이터 나열

Linked List -> 각각의 공간에 존재하는 데이터를 연결해서 관리

 

- Linked List의 구성 요소 및 용어

 

노드(Node) : 데이터 저장 단위 -> 데이터 값, 포인터로 구성

     -> 포인터(Pointer) : 노드 끼리의 연결 정보 저장

헤드(Head) : Linked List의 시작을 의미, 데이터 값으로 NULL을 가짐

 

 

 

Linked List 기본 구성 요소 구현

 

- Attribution ( 속성 )

 

Linked List의 구성 요소 : head, node, pointer

Node의 구성 요소 : value(값), pointer

 

-> Node 클래스 생성

-> Linked List 클래스 생성

-> Node 클래스 상속

 

1. Node 클래스 생성자 ( Attribution )

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

2. Linked List 클래스 생성자 ( Attribution )

-> 노드 상속

class Linked_List:
    def __init__(self):
        self.head = Node(None)

 

- Method ( 주요 기능 )

 

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

class Linked_List:
    def __init__(self):
        self.head = Node(None)
    def addlist(self, value):
        new_node = Node(value)
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
    def deletenode(self, idx):
        target = 0
        prev_node = self.head
        if prev_node.next is None:
            return print("List is Empty")
        next_node = prev_node.next
        while next_node.next is not None and target != idx:
            next_node = next_node.next
            prev_node = prev_node.next
            target += 1
        prev_node.next = next_node.next
        return print(f"{idx}th node delete, value : {next_node.data}")
    def find(self, value):
        current_node = self.head
        idx = -1
        while current_node is not None:
            if current_node.data == value:
                return print(f"Node at {idx}")
            current_node = current_node.next
            idx += 1
        return print("Node not found")
    def size(self):
        current_node = self.head
        res = 0
        while current_node.next:
            current_node = current_node.next
            res += 1
        return print(f"size : {res}")
    def printlist(self):
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
            print(current_node.data, end=" ")
        print()

ls1 = Linked_List()
ls1.addlist(1)
ls1.addlist(2)
ls1.addlist(3)
ls1.addlist(4)
ls1.printlist()
# 출력 : 1 2 3 4
ls1.find(1)
# 출력 : Node at 0
ls1.deletenode(0)
# 출력 : 0th node delete, value : 1
ls1.find(1)
# 출력 : Node not found
ls1.printlist()
# 출력 : 2 3 4
ls1.size()
# 출력 : size : 3