파이썬으로 링크드 리스트 구현하기

1. 링크드 리스트란?

- 배열의 단점을 극복하기 위해 만들어짐

- 배열은 미리 메모리 사이즈를 할당하고 사용해야 함

- 메모리할당을 미리예약하지않고 필요할때마다 데이터를 추가추가할수 있는 구조

- 데이터 + next 데이터를 가르킬 주소를 하나의 데이터라고 보면 된다.

- 그런테 이것을 데이터라고 부를수 없어 데이터와 주소를 하나로 부르는 것을 노드라고 한다.

- 다음 데이터를 가르킬 주소라고 하기도 하지만 포인터라고 얘기한다.

링크드 리스트는 노드와 노드의 연결이다.

노드는 데이터와 다음 노드의 연결정보를 갖는 공간이다.

2. 링크드 리스트 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
    
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
    
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
    
    def delete(self, data):
        # 헤드값 없을때
        if self.head == '':
            print("해당값을 가진 노드가 없습니다.")
            return
 
        # 지우는값이 헤드값일때
        if self.head.data == data:
            tmp = self.head
            self.head = self.head.next
            del tmp
        else:
            # 지우는 값이 중간값일때
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next
 
linkedlist1 = NodeMgmt(0) # 0
linkedlist1.add(1) # 0 1
linkedlist1.add(2) # 0 1 2
linkedlist1.add(3) # 0 1 2 3
 
linkedlist1.desc() # 0 1 2 3
 
linkedlist1.delete(1) # 0 2 3
 
linkedlist1.desc() # 0 2 3

링크드 리스트는 데이터가 계속 체이닝 되어서 찾아가는것인데

노드가 10000개 있고 찾으려는 데이터값이 9000번대에 있다면 

맨 앞에서부터 링크드 되어있는 리스트의 값을 찾아가야 한다.  

하지만 뒤에서부터 찾는다면 1000번만 찾으면 값을 찾을 수 있다.

prev, tail을 갖는 것이 더블 링크드 리스트이다.

더블링크드 리스트는 추후에 정리할 예정이다.