포인터를 이용한 연결 리스트

노드마다 뒤쪽 노드를 가리키는 포인터가 포함되도록 구현하는 연결 리스트를 알아보자

연결리스트는 대부분의 알고리즘에서 사용하는 기본 자료구조이다. 알고리즘에서 사용하는 데이터와 다음 노드를 가리키는 링크를 묶어서 노드로 정의하여 사용한다. c/c++에서는 포인터(pointer) 개념으로 링크를 사용하지만 파이썬은 포인터라는 개념이 없다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
# 파이썬에서 노드는 위와같이 구현하였다. 
# 위 구조에서 현재 노드에서 다음 노드를 어떻게 참조 시킬 수 있을까?

head = Node(5)
next_node = Node(12)
head.next = next_node

# 위와같이 구현하여 참조시킬 수 있다. 
# 이제 위와같이 노드를 생성하고 관리하는 클래스를 구현하여 사용할 것이다.

출처 : 링크

포인터로 연결 리스트 만들기

연결 리스트에 데이터를 삽일할 때 노드용 인스턴스를 생성하고, 데이터를 삭제할 때 노드용 인스턴스를 없애면 앞에서 제시한 데이터를 옮기는 문제를 해결할 수 있다.

• Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있다.

• Pointer : 각 노드에서 다음 데이터를 가리키는 주소값을 가진다.

• Head : 링크드리스트에서 가장 시작점인 데이터를 의미한다.

• Tail : 링크드리스트에서 가장 마지막 데이터를 의미

• Next=None(또는 Null) : 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다.

출처: https://ybworld.tistory.com/85 [투손플레이스]

링크드 리스트 만들기

1. 노드 생성

class Node:
    """연결 리스트용 노드 클래스"""

    def __init__(self, data: Any = None, next: Node = None):
        """초기화"""
        self.data = data  # 데이터
        self.next = next  # 뒤쪽 포인터

2. Node 연결리스트 클래스 생성

class LinkedList:
    """연결 리스트 클래스"""

    def __init__(self) -> None:
        """초기화"""
        self.no = 0          # 노드의 개수
        self.head = None     # 머리 노드
        self.current = None  # 주목 노드

    def __len__(self) -> int:
        """연결 리스트의 노드 개수를 반환"""
        return self.no

3. search() / 검색에 성공하면 발견할 수 있는 노드

def search(self, data: Any) -> int:
        """data와 값이 같은 노드를 검색"""
        cnt = 0
        ptr = self.head
        while ptr is not None:
            if ptr.data == data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1

    def __contains__(self, data: Any) -> bool:
        """연결 리스트에 data가 포함되어 있는가?"""
        return self.search(data) >= 0

4. add_first() / 삽입한 머리 노드

    def add_first(self, data: Any) -> None:
        """맨 앞에 노드를 삽입"""
        ptr = self.head  # 삽입 전의 머리 노드
        self.head = self.current = Node(data, ptr)
        self.no += 1

5. add_last() / 삽입한 꼬리 노드

    def add_last(self, data: Any):
        """맨 끝에 노드를 삽입"""
        if self.head is None :    # 리스트가 비어 있으면
            self.add_first(data)  # 맨앞에 노드 삽입
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next  # while문을 종료할 때 ptr은 꼬리 노드를 참조
            ptr.next = self.current = Node(data, None)
            self.no += 1

6. remove_first() / 삭제한 뒤 머리노드(리스트가 비어 있으면 None)

    def remove_first(self) -> None:
        """머리 노드를 삭제"""
        if self.head is not None:  # 리스트가 비어 있으면
            self.head = self.current = self.head.next
        self.no -= 1

7. remove_last() / 삭제한 뒤 꼬리녿(리스트가 비어 있으면 None)

    def remove_last(self):
        """꼬리 노드 삭제"""
        if self.head is not None:
            if self.head.next is None :  # 노드가 1개 뿐이라면
                self.remove_first()      # 머리 노드를 삭제
            else:
                ptr = self.head  # 스캔 중인 노드
                pre = self.head  # 스캔 중인 노드의 앞쪽 노드

                while ptr.next is not None:
                    pre = ptr
                    ptr = ptr.next # while문 종료시 ptr은 꼬리 노드를 참조하고 pre는 맨끝에서 두 번째 노드를 참조
                pre.next = None  # pre는 삭제 뒤 꼬리 노드
                self.current = pre
                self.no -= 1

8. remove() / 삭제한 노드의 앞쪽 노드

def remove(self, p: Node) -> None:
        """노드 p를 삭제"""
        if self.head is not None:
            if p is self.head:       # p가 머리 ​​노드이면
                self.remove_first()  # 머리 노드를 삭제
            else:
                ptr = self.head

                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return  # ptr은 리스트에 존재하지 않음
                ptr.next = p.next
                self.current = ptr
                self.no -= 1

9. remove_current_node() / 삭제한 노드의 앞쪽 노드

    def remove_current_node(self) -> None:
        """주목 노드를 삭제"""
        self.remove(self.current)

10. clear()

    def clear(self) -> None:
        """전체 노드를 삭제"""
        while self.head is not None:  # 전체가 비어 있게 될 때까지
            self.remove_first()       # 머리 노드를 삭제
        self.current = None
        self.no = 0

11. next()

    def next(self) -> bool:
        """주목 노드를 한 칸 뒤로 진행"""
        if self.current is None or self.current.next is None:
            return False  # 진행할 수 없음
        self.current = self.current.next
        return True

12. print_current_node() & print()

    def print_current_node(self) -> None:
        """주목 노드를 출력"""
        if self.current is None:
            print('주목 노드가 존재하지 않습니다.')
        else:
            print(self.current.data)

    def print(self) -> None:
        """모든 노드를 출력"""
        ptr = self.head

        while ptr is not None:
            print(ptr.data)
            ptr = ptr.next

다른 예시코드

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

    def __str__(self):
        return str(self.data)

class SingleLinkedList:
    def __init__(self, data):
        new_node = Node(data)
        self.head = new_node
        self.list_size = 1

    def __str__(self):
        print_list = '[ '
        node = self.head
        while True:
            print_list += str(node)
            if node.next == None:
                break
            node = node.next
            print_list += ', '
        print_list += ' ]'
        return print_list

    def insertFirst(self, data):
        new_node = Node(data)
        temp_node = self.head
        self.head = new_node
        self.head.next = temp_node
        self.list_size += 1

    def insertMiddle(self, num, data):
        if self.head.next == None:
            insertLast(data)
            return
        node = self.selectNode(num)
        new_node = Node(data)
        temp_next = node.next
        node.next = new_node
        new_node.next = temp_next
        self.list_size += 1

    def insertLast(self, data):
        node = self.head
        while True:
            if node.next == None:
                break
            node = node.next

        new_node = Node(data)
        node.next = new_node
        self.list_size += 1

    def selectNode(self, num):
        if self.list_size < num:
            print("Overflow")
            return
        node = self.head
        count = 0
        while count < num:
            node = node.next
            count += 1
        return node

    def deleteNode(self, num):
        if self.list_size < 1:
            return # Underflow
        elif self.list_size < num:
            return # Overflow

        if num == 0:
            self.deleteHead()
            return
        node = self.selectNode(num - 1)
        node.next = node.next.next
        del_node = node.next
        del del_node

    def deleteHead(self):
        node = self.head
        self.head = node.next
        del node

    def size(self):
        return str(self.list_size)

if __name__ == "__main__":
    m_list = SingleLinkedList(1)
    m_list.insertLast(5)
    m_list.insertLast(6)
    print('LinkedList :', m_list)
    print('LinkedList Size() :', m_list.size())
    print('LinkedList SelectNode(1) :', m_list.selectNode(1))

    m_list.insertMiddle(1, 15)
    print('LinkedList Insert Middle(1, 15) :', m_list)

    m_list.insertFirst(100)
    print('LinkedList Insert First(100) : ', m_list)
    print('LinkedList SelectNode(0) :', m_list.selectNode(0))

    m_list.deleteNode(0)
    print('LinkedList Delete Node(0) : ', m_list)
    m_list.deleteNode(1)
    print('LinkedList Delete Node(1) : ', m_list)
    
#LinkedList : [ 1, 5, 6 ]
#LinkedList Size() : 3
#LinkedList SelectNode(1) : 5
#LinkedList Insert Middle(1, 15) : [ 1, 5, 15, 6 ]
#LinkedList Insert First(100) :  [ 100, 1, 5, 15, 6 ]
#LinkedList SelectNode(0) : 100
#LinkedList Delete Node(0) :  [ 1, 5, 15, 6 ]
#LinkedList Delete Node(1) :  [ 1, 15, 6 ]
    

예시코드 출처 : 링크