[파이썬] Linked list

1. 데이터를 순서대로 저장해준다.

2. 요소를 계속 추가할 수 있다.

 

 

 

쉽게 비유하면 이렇다.

이런식으로 숫자를 작은 수 부터 나열하고 싶을 때 규리가 2를 가지고있으면 가지고 있는 뒤 테이블에 다음으로 작은 숫자를 가진 이름을 넣어두면 일렬로 정렬되는 것이다.

이렇게 연결된 박스들의 순서는 규리 - 태호 - 동욱 - 유나 - 현승 순으로 연결된다.

 

 

🤔 노드(Node)

 

 

data는 가지고 있는 변수와 같은 요소값이 들어가고 next에는 다음 노드의 레퍼런스가 들어간다. 

가장 첫번째 노드의 주소를 알면 흩어져 있는 노드들을 가져올 수 있다.

가장 첫번째의 노드를 Head 노드라고 한다. 실제 메모리에는 여기저기 흩어져 있다는 것을 인지하자.

 

🤔 노드 클래스 만들기

 

class Node:
    """링크드 리스트의 노드 클래스"""

    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스


 # 데이터 2, 3, 5, 7, 11을 담는 노드들 생성
 head_node = Node(2)
 node_1 = Node(3)
 node_2 = Node(5)
 node_3 = Node(7)
 tail_node = Node(11)

 # 노드들을 연결
 head_node.next = node_1
 node_1.next = node_2
 node_2.next = node_3
 node_3.next = tail_node

 #노드 순서대로 출력
 iterator = head_node

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

 

🤔 링크드 리스트 만들기

 

class Node:
    """링크드 리스트의 노드 클래스"""

    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스


class LinkedList:
    """링크드 리스트 클래스"""

    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        """링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        if self.head is None:  # 링크드 리스트가 비어 있는 경우
            self.head = new_node
            self.tail = new_node
        else:  # 링크드 리스트가 비어 있지 않은 경우
            self.tail.next = new_node
            self.tail = new_node

 # 새로운 링크드 리스트 생성
 my_list = LinkedList()

 # 링크드 리스트에 데이터 추가
 my_list.append(2)
 my_list.append(3)
 my_list.append(5)
 my_list.append(7)
 my_list.append(11)

 iterator = my_list.head

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

 

🤔 링크드 리스트 __str__ 메소드

 

class Node:
    """링크드 리스트의 노드 클래스"""
    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스


class LinkedList:
    """링크드  리스트 클래스"""

    def __init__(self):
        self.head = None  # 링크드 리스트의 가장 앞 노드
        self.tail = None  # 링크드 리스트의 가장 뒤 노드

    def append(self, data):
        """링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        # 링크드 리스트가 비어 있으면 새로운 노드가 링크드 리스트의 처음이자 마지막 노드다
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        # 링크드 리스트가 비어 있지 않으면
        else:
            self.tail.next = new_node  # 가장 마지막 노드 뒤에 새로운 노드를 추가하고
            self.tail = new_node  # 마지막 노드를 추가한 노드로 바꿔준다

    def __str__(self):
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        # 링크드  리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
        iterator = self.head

        # 링크드  리스트 끝까지 돈다
        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더해준다
            res_str += f" {iterator.data} |"
            iterator = iterator.next  # 다음 노드로 넘어간다

        return res_str

 # 새로운 링크드 리스트 생성
 linkedList = LinkedList()

 # 링크드 리스트에 데이터 추가
 linkedList.append(2)
 linkedList.append(3)
 linkedList.append(5)
 linkedList.append(7)
 linkedList.append(11)

 print(linkedList)

 여기서 쓰인 f string은

name = "cat" / age = 13 / address = "Korea" 가 초기화 되어 있을 때

f"{name}은 {age}살이고 {address}에 있음" 이라고 변수에 저장후 출력시

cat은 13살이고 Korea에 있음으로 출력됨. 굉장히 편리하지만 파이썬 3.6 버전부터 쓸 수 있다.

| 2 | 3 | 5 | 7 | 11 |