더 복잡해져서 돌아온 연결 리스트

https://koreanraichu.tistory.com/312

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

부트캠프 들으면서 얘를 구현해 볼 기회가 또 생겼음. 전에 했던것보다 훨배 복잡한거라 들고 왔습니다. 아마 다음에 올리는건 트리랑 그래프정도?

---

# 노드
class Node:
    # 뾰로롱
    def __init__ (self, _value):
        self.value = _value
        self.nextnode = None
        
    # 다음 노드의 주소값을 설정 
    def setnext(self,_nextnode):
        self.nextnode = _nextnode

얘는 노드 만드는 애다. 연결 리스트는 노드 하나 안에 노드가 담을 정보와 다음 노드 주소(다음 노드 여기 있음)가 들어있다.

 

class Linkedlist:
    # 머리
    def __init__ (self):
        self.headnode = Node(0)
        self.datacount = 0 # 연결 리스트의 길이
    
    # 데이터 넣기
    def add_node (self, _value):
        # 새로운 노드 생성
        new_node = Node(_value)
        pointernode = self.headnode
        # 마지막 노드가 어디 있나
        while True:
            # 찾았으면 뒤에 추가해라 
            if pointernode.nextnode == None: 
                break
            else: 
                pointernode = pointernode.nextnode
        pointernode.nextnode = new_node
        # 카운터 추가
        self.datacount += 1

    # 내놔
    def where_node (self, _position): 
        target_index = _position - 1
        # 잘못 입력했다면
        if _position < 1: 
            print('순서값은 1보다 같거나 큰 정수입니다. ')
            return
        elif _position > self.datacount:
            print(f'범위는 1부터 {self.datacount}까지입니다. ')
            return
        # 여기가 본론임... 
        else: 
            # 헤드에서 시작해서 우리가 찾는 포지션 값까지 가야 한다. 
            pointernode = self.headnode
            # 전체 이동 횟수를 계산하고 
            move_cnt = target_index + 1
            # 그만큼 반복 아... 
            for i in range(move_cnt):
                # 가야돼 아... 
                pointernode = pointernode.nextnode
            # 드디어 나옴 
            return pointernode.value
        
    # 여기다 넣어줘
    def insert_node (self, _position, _value):
        # 수정할 포지션
        target_index = _position - 1 # 3 입력하면 3번째 수정하려면 필요함 
        # prev: 하나 덜 감/curr: 정직하게 ㄱㄱ
        # 2번때에 노드 끼워넣는거면 1, 2까지 갑니다. 
        if _position < 1: 
            print('순서값은 1보다 같거나 큰 정수입니다. ')
            return
        elif _position > self.datacount:
            # 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨? 
            print(f'범위는 1부터 {self.datacount}까지입니다. ')
            return
        else: 
            # 끼워넣을 노드
            new_node = Node(_value)
            # 노드를 끼워넣을 포지션과 그 앞 노드에 대한 정보가 필요함
            # 그래서 두개지요 
            prev_pointer = self.headnode
            curr_pointer = self.headnode.nextnode
            move_cnt = target_index
            for i in range(move_cnt):
                prev_pointer = prev_pointer.nextnode
                curr_pointer = curr_pointer.nextnode
            # 노드 끼우는 순서: prev-노드-curr
            prev_pointer.nextnode = new_node
            new_node.nextnode = curr_pointer
            # 아 맞다 카운터
            self.datacount += 1
            return 

    # 바꿔줘
    def change_node (self, _position, _value):
        # 3을 입력하면 정직하게 2번째 인덱스를 바꾸기 위해서는 변환 절차가 필요하다. 
        target_index = _position - 1
        if _position < 1: 
            print('순서값은 1보다 같거나 큰 정수입니다. ')
            return
        elif _position > self.datacount:
            # 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨? 
            print(f'범위는 1부터 {self.datacount}까지입니다. ')
            return
        else: 
            # 원리는 간단하다. 찾아라, 그리고 바꿔라. 
            move_cnt = target_index + 1
            pointernode = self.headnode
            for i in range(move_cnt):
                pointernode = pointernode.nextnode
            # 도착했으면 수정을 해야됩니다. 
            pointernode.value = _value

    # 빼줘
    def delete_node (self, _position): 
        # 3을 입력하면 정직하게 2번째 인덱스를 지우기 위해서는 변환 절차가 필요하다. 
        target_index = _position - 1
        if _position < 1: 
            print('순서값은 1보다 같거나 큰 정수입니다. ')
            return
        elif _position > self.datacount:
            # 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨? 
            print(f'범위는 1부터 {self.datacount}까지입니다. ')
            return
        else: 
            # 그 포인터 앞에 있는 노드의 연결을 다음다음노드로 하면 된다. 연결만 끊으면 끝. 
            move_cnt = target_index
            pointernode = self.headnode
            for i in range(move_cnt):
                pointernode = pointernode.nextnode
            pointernode.nextnode = pointernode.nextnode.nextnode
            # 아 맞다 카운터
            self.datacount -= 1
            return

    # 잘 된겨? 
    def node_show (self):
        # 헤드노드의 다음 노드가 없으면
        if self.headnode.nextnode == None:
            print('이 리스트는 텅 비었습니다. ')
            return 
        
        pointernode = self.headnode

        while True:
            # 다음으로 렛츄고
            pointernode = pointernode.nextnode
            print(pointernode.value)
            # 없으면 시마이
            if pointernode.nextnode == None:
                break
        return

본론은 여기 있다. 이게 다 머여!! 하나씩 알아봅시다... 이게 이래뵈도 OOP 서타일인데, 그거는 또 나중에 기회가 되면 얘기해주겠음.

 

머리 머리 머리

# 머리
def __init__ (self):
    self.headnode = Node(0)
    self.datacount = 0 # 연결 리스트의 길이

연결 리스트는 머리와 꼬리가 있다. 머리는 말 그대로 연결 리스트의 시발점이고, 앞 노드가 없다. 반대로 꼬리는 다음 노드의 주소를 갖고 있지 않고, 연결 리스트 맨 뒤에 있다.

 

노드 추가

# 데이터 넣기
def add_node (self, _value):
    # 새로운 노드 생성
    new_node = Node(_value)
    pointernode = self.headnode
    # 마지막 노드가 어디 있나
    while True:
        # 찾았으면 뒤에 추가해라 
        if pointernode.nextnode == None: 
            break
        else: 
            pointernode = pointernode.nextnode
    pointernode.nextnode = new_node
    # 카운터 추가
    self.datacount += 1

리스트를 만들고 거기에 노드를 추가하려면 쟤가 필요하다. 기본적으로 맨 앞... 그니까 헤드를 만들 때를 빼면 연결 리스트에 새 노드를 추가하는 과정은 1) 새 노드를 만들고 2) 새 노드와의 연결점을 맨 뒤 노드에 추가한다 이다. 얘는 그래도 좀 심플한 편이여...

 

특정 번호로 노드 찾기

# 내놔
def where_node (self, _position): 
    target_index = _position - 1
    # 잘못 입력했다면
    if _position < 1: 
        print('순서값은 1보다 같거나 큰 정수입니다. ')
        return
    elif _position > self.datacount:
        print(f'범위는 1부터 {self.datacount}까지입니다. ')
        return
    # 여기가 본론임... 
    else: 
        # 헤드에서 시작해서 우리가 찾는 포지션 값까지 가야 한다. 
        pointernode = self.headnode
        # 전체 이동 횟수를 계산하고 
        move_cnt = target_index + 1
        # 그만큼 반복 아... 
        for i in range(move_cnt):
            # 가야돼 아... 
            pointernode = pointernode.nextnode
        # 드디어 나옴 
        return pointernode.value

리스트로 치자면 인덱싱이다. 이 코드에는 약간의 변형을 했는데, 원래는 연결 리스트의 3번째 노드에 들어있는 값을 보고 싶으면 2를 입력해야 하는데(콤퓨타는 0부터 셈) 이게 너무 직관적이지 않은겨... 헷갈려요 사람... 그래서 3 입력하면 3번째 노드의 값이 나오게끔 변형했다.

 

그럼 특정 번호로 노드를 찾는 과정에 대해 알아보자… 뭐 사실 알아보고 자시고 할 것도 없이 찾을 순번 될 때까지 반복문 도는 게 다긴 한데… 왜 이렇게까지 해야 하나요? 연결 리스트는 원래 그렇습니다. 배열은 일렬로 줄줄이 소세지라서 걍 첫 번째 값 찾고 하나 둘 셋 하면 되지만 쟤는 얘는 여기있고 얘 따라가면 여기있고 걔 따라가면 또 여기있고…가 꼬리까지 반복이다. 연결 리스트는 삭제, 수정, 추가가 상대적으로 용이한 대신 탐색이 좀 오래 걸리는데, 특히나 찾을 노드가 뒤에 있을수록 더 오래 걸린다. 3번 노드면 0->1->2->3만 가면 되지만 7번 노드면 0->1->2->3->4->5->6->7이거든.

 

사이에 끼워넣기

# 여기다 넣어줘
def insert_node (self, _position, _value):
    # 수정할 포지션
    target_index = _position - 1 # 3 입력하면 3번째 수정하려면 필요함 
    # prev: 하나 덜 감/curr: 정직하게 ㄱㄱ
    # 2번때에 노드 끼워넣는거면 1, 2까지 갑니다. 
    if _position < 1: 
        print('순서값은 1보다 같거나 큰 정수입니다. ')
        return
    elif _position > self.datacount:
        # 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨? 
        print(f'범위는 1부터 {self.datacount}까지입니다. ')
        return
    else: 
        # 끼워넣을 노드
        new_node = Node(_value)
        # 노드를 끼워넣을 포지션과 그 앞 노드에 대한 정보가 필요함
        # 그래서 두개지요 
        prev_pointer = self.headnode
        curr_pointer = self.headnode.nextnode
        move_cnt = target_index
        for i in range(move_cnt):
            prev_pointer = prev_pointer.nextnode
            curr_pointer = curr_pointer.nextnode
        # 노드 끼우는 순서: prev-노드-curr
        prev_pointer.nextnode = new_node
        new_node.nextnode = curr_pointer
        # 아 맞다 카운터
        self.datacount += 1
        return

사이에 끼워넣는다는 건 1) 얘랑 2) 쟤(얘 앞에 있음) 사이에 노드를 새로 끼워넣는다는 얘기인데, 이건 어떻게 하느냐... 원리 자체는 간단하다. 앞의 노드 포인터를 추가할 애를 가리키게 하고, 추가할 애의 포인터가 뒤 노드를 가리키게 하면 된다. 그러니까 A와 B 사이에 C를 넣을거면 A의 포인터는 C를, C의 포인터는 B를 가리키게 하면 되는 것이다. 근데 뭐가 문제냐고? 저 노드들 출발선을 조절해야 할 거 아뉴... 반복문을 두 노드가 같이 돌게 되면 같은 횟수를 순회해야된다 이거지.

 

prev_pointer = self.headnode
curr_pointer = self.headnode.nextnode

여기서 prev_pointer보다 curr_pointer가 하나 앞으로 가야 한다. 근데 둘이 출발선상이 같으면 종점이 같아지잖아요? 그러니까 하나 앞으로 가야 하는 노드는 출발선을 하나 앞으로 땡기면 된다는거다. 이거 두개 앞으로 땡기면 넥스트 넥스트 달아야되나... 백준 그 롱롱롱롱롱롱롱롱인가 그거냐 

 

노드가 담은 값 바꾸기

# 바꿔줘
def change_node (self, _position, _value):
    # 3을 입력하면 정직하게 2번째 인덱스를 바꾸기 위해서는 변환 절차가 필요하다. 
    target_index = _position - 1
    if _position < 1: 
        print('순서값은 1보다 같거나 큰 정수입니다. ')
        return
    elif _position > self.datacount:
        # 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨? 
        print(f'범위는 1부터 {self.datacount}까지입니다. ')
        return
    else: 
        # 원리는 간단하다. 찾아라, 그리고 바꿔라. 
        move_cnt = target_index + 1
        pointernode = self.headnode
        for i in range(move_cnt):
            pointernode = pointernode.nextnode
        # 도착했으면 수정을 해야됩니다. 
        pointernode.value = _value

뺑뺑이 도는 건 똑같은데 걍 도착해서 값만 바꾸면 된다.

 

노드 삭제

# 빼줘
def delete_node (self, _position): 
    # 3을 입력하면 정직하게 2번째 인덱스를 지우기 위해서는 변환 절차가 필요하다. 
    target_index = _position - 1
    if _position < 1: 
        print('순서값은 1보다 같거나 큰 정수입니다. ')
        return
    elif _position > self.datacount:
        # 리스트 길이를 벗어나면... 아니 근데 그러면 걍 끼워넣기 하면 안됨? 
        print(f'범위는 1부터 {self.datacount}까지입니다. ')
        return
    else: 
        # 그 포인터 앞에 있는 노드의 연결을 다음다음노드로 하면 된다. 연결만 끊으면 끝. 
        move_cnt = target_index
        pointernode = self.headnode
        for i in range(move_cnt):
            pointernode = pointernode.nextnode
        pointernode.nextnode = pointernode.nextnode.nextnode
        # 아 맞다 카운터
        self.datacount -= 1
        return

연결 리스트에서 노드를 삭제하는 것도 원리 자체는 간단하다. 포인터가 다음다음 노드를 가리키게 하면 된다. 그러니까 A-B-C에서 B를 지우고 싶으면 A의 포인터가 C를 가리키게 하면 된다. 쉽죠? 솔직히 인서트 하고 나면 쟤는 선녀야...

 

전체 조회

# 잘 된겨? 
def node_show (self):
    # 헤드노드의 다음 노드가 없으면
    if self.headnode.nextnode == None:
        print('이 리스트는 텅 비었습니다. ')
        return 
    
    pointernode = self.headnode

    while True:
        # 다음으로 렛츄고
        pointernode = pointernode.nextnode
        print(pointernode.value)
        # 없으면 시마이
        if pointernode.nextnode == None:
            break
    return

이건 뭐 별 거 없고, 연결 리스트를 머리부터 꼬리까지 쭉 돌면서 노드가 담고 있는 값을 출력하는 코드다. 연결 리스트의 꼬리는 다음으로 이어지는 게 없으니까 포인터 없어? 끝! 이 되는 것. 쉽죠?