Python으로 연결 리스트 구현하기

https://koreanraichu.tistory.com/311

연결 리스트

여기서는 대충 이론적인 설명(...)을 했다면 이제 만들어보자. 이게 왜 분리가 됐냐면 티스토리와 워드프레스는 이론 카테고리와 코딩 카테고리가 나뉘어져 있다.

---

오늘의 참고문헌은 

https://velog.io/@yeseolee/python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List-feat.LeetCode

[Python 자료구조] 연결리스트(Linked List) feat.LeetCode

https://wikidocs.net/191324

03. 파이썬으로 연결 리스트 구현하기

여기다. 여기 좋은거 많데? 근데 구슬이 서 말이라도 꿰어야 보배라는데... 뭐함? IDE 켜야죠.

 

class node:
    def __init__(self, data):
        self.data = data # 노드에 들어갈 데이터 
        self.next = None # 다음 노드를 가리킬 포인터

연결 리스트는 노드로 이루어져 있고, 그 노드는 데이터와 포인터로 구성되어있다. 그니까 모든 노드들이 다 이래요. 헤드(시작) 테일(끝) 뭐 다를거 없이 걍 다 노드는 똑같다. 단지 테일 노드는 포인터가 다음을 가리키지 않을 뿐. 그러면 이거 찍어내야 할 거 아뉴? 그죠 노드 찍어낼라면 틀 짜야지.

 

head = node(1) # 헤드(첫 노드)
head.next = node(2) # 다음 노드
head.next.next = node(3) # 다음다음 노드

다른거 없고 이렇게만 해도 노드가 세 개인 연결 리스트가 생긴다. 노드는 데이터와 포인터로 이루어져 있다고 했는데, 여기서 데이터는 각각 1, 2, 3이다. 그리고 next로 노드 1의 포인터가 2를, 2의 포인터가 3을 가리키게 했다. 

 

node = head
while node:
    print(node.data)
    node = node.next

요 네 줄 추가하면 출력도 된다. while문은 대충 뭘 가리키는 애가 없는 노드(테일)까지 갈 때까지 데이터를 출력하고 다음 노드로 가시오 뭐 이런 얘기.

 

근데 생각해보자. 저 넥스트를 꼭 연결 리스트 만들때마다 줄줄이 소시지마냥 추가해야됨? 저거 백준 문제에서 본 적 있다고요? 네, 그 롱롱롱ㄹ오롱ㄹ오롱롱롱롱 그 문제임... 아무튼 일할때도 잔머리를 굴리는 본인 성미상 이런건 씁 에반데 소리가 절로 나온다. 다들 그렇잖음?

head = node("Pikachu")

여기 연결 리스트가 있다. 그래서 이 뒤에 피카츄의 진화체인 라이츄를 추가해볼건데... 사실 간단하게 head.next = node("raichu") 해도 되긴 된다. 근데 저게 막 25번째 노드고 그러면 넥스트 24번 정직하게 치실거임? 아니잖음...

 

node = head
while node:
    print(node.data)
    if node.next == None:
        node.next = Node("Raichu")
        break
    node = node.next

출력이 피카츄만 나와서 글치 추가된 거 맞다. 위에 있는 while문을 조금 응용한건데, 테일 노드(하나밖에 없음...)에 도달하면 뒤에 라이츄 노드를 붙이게 된다. 그럼 헤드에 뭐 추가할때는 어떻게 하나요?

 

node = Node("Pichu")
node.next = head
head = node

이건 세 단계로 헤드를 바꾼(...)건데, 먼저 피츄 노드를 추가하고 피츄 노드의 포인터를 피카츄(지금 헤드)를 가리키게 한 다음 피츄 노드를 헤드로 임명했다. 라이츄는 밑에 따로 추가한거라 출력 안되는데 추가된거 맞음. 근데 왜 출력이 안될까...

 

빌형! VScode 이상해!

 

아, 사실 참고문헌에는 추가만 있어서 삭제도 따로 찾아봤다.

head = Node("Pidgey")
head.next = Node("Cyndaquil")
head.next.next = Node("Totodile")

2세대 스타팅들이 있는 노드인데 자세히 보니까... 구구가 아니라 치코리타가 와야 하는 거 아녀? 반대 아닌가 

 

node = head
while node:
    if node.data == "Pidgey":
        head = head.next
        node = node.next
        break
    node = node.next

데이터가 구구면 다음 노드가 머리가 된다 뭐 이런 얘기인데, 이거는 구구 노드가 헤드라 가능한 코드다. 원래는

node = head
while node:
    if node.next.data == 5:
        node.next = node.next.next
        break
    node = node.next

다음 노드가 내가 찾는 값이면 그거 빼고 다음다음노드로 연결해서 지운다.