LinkedList

C++에서는 링크드리스트를 구현하기 위해서 포인터를 직접 사용해 주소값에 접근하지만, 파이썬은 그럴 필요가 없음

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
        
class LinkedList:
    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)    	

먼저 C++과 동일하게 노드를 만들어주는데, struct를 통해 만드는 것과는 다르게 쉽고 간편하게 class로 만들어줄 수 있음

next의 기본값은 null이 아니라 None임

그 후 Node를 써먹는 LinkedList 클래스를 만들어주고,
__init__ 함수에서 head를 만듦

head는 LinkedList를 순회할 때 사용할 시작점을 의미

Add

    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)   

이 부분에서,

if self.head == '':
	self.head = Node(data)

이 부분은, head가 ''인 상황, 즉, 첫번째 Node일 경우에 대한 처리방법
한마디로, Node(data)가 첫번째 노드니, head로 그것을 그냥 가리킴

else:
    node = self.head
    while node.next:
        node = node.next
    node.next = Node(data)   

이 부분은 head가 이미 가리키는 노드가 있을 때 사용
head를 node에 넣고 시작점을 파악, head자체는 처음을 가리키므로 움직여선 안 되기 때문에 다른 변수에 넣고 사용해줘야 함 node를 움직이면, head값은 변하지 않기 때문

그렇게 while문을 돌면, 더이상 넘어갈 수 없어지는 즉, node.next == ''인 상황이 나옴 그 부분은 LinkedList의 끝자락이므로, node.next = Node(data)로 새로운 Node를 연결시켜줌

Display

def display(self):
    node = self.head
    while node:
        print(node.data)
        node = node.next

이 함수 역시 LinkedList클래스에 추가할 수 있는데, 리스트의 처음부터 끝까지 모든 Node.data를 출력해줌

이 역시 head를 사용하기 때문에 head의 정보를 받아올 변수를 쓰고, head자체는 변경해서는 안 되는 걸 명심

Delete

def delete(self, data):
    if self.head == '': #빈 연결리스트
        return False
    
    if self.head.data == data: # 지우고자 하는 노드가 맨 앞
        temp = self.head
        self.head = self.head.next
        del temp
        return True
        
    node = self.head
    while node.next:
        if node.next.data == data:
            temp = node.next
            node.next = node.next.next
            del temp
            return True # 지우고자 하는 노드를 찾아 지웠을 경우
        node = node.next
    
    #지우고자 하는 노드가 없을 경우
    return False

delete의 경우 조금 어려운게, 다음 네가지를 모두 생각해야 함

• LinkedList가 모두 비어있을 경우
• LinkedList의 첫번째 Node가 비워야 할 값인 경우
• LinkedList의 제일 끝 아니면 도중에 Node가 있어 지울 경우
• 끝까지 다 찾아봐도 지워야 할 데이터를 찾을 수 없을 경우

물론 add도 특정 위치나, 특정 데이터 뒤에 넣어야 하는 순간 조금 난이도가 상승함
특정 데이터 뒤에 넣는 코드

Add after

def insert_data(self, data, before):
    if self.head == '': #빈 리스트의 경우
        return False # 직전 데이터가 없으므로 False 리턴
    
    node = self.head # 비지 않은 리스트에 모두 해당
    while node:
        if node.data == before: # 직전 노드의 데이터가 before인 경우
            new = Node(data)
            new.next = node.next # 직전 노드가 가리키던 걸 new가 대신 가리킴
            node.next = new # 그러고 나서 직전 노드가 new를 가리키게 함
            return True #삽입에 성공했으므로 True 리턴
    	node = node.next  

위 코드를 사용하면 이제 before에 직전 데이터 값을 넣어주고 data에 넣어야 할 값을 넣어줘서, 맨 앞을 제외한 중간, 끝에 모두 데이터 삽입이 가능해짐