[Data Structure] Linked List - 링크드 리스트

node - 노드

 

링크드 리스트란 노드란 것을 사용해서 구현한 하나의 자료구조이다.

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

노드의 경우 위의 코드와 같이 생겼으며 생성자를 통해 구성을 살펴보자. 노드의 경우 두 가지 인자를 바탕으로 생성이 된다. 하나는 노드에서 담고자 하는 데이터를 저장하는 변수, 그리고 또 하나는 그다음에 올 노드의 정보를 담는 변수의 방식으로 생성이 된다. 노드의 경우 배열처럼 하나의 지정된 공간에 여러 가지 데이터를 담아두는 그런 자료구조가 아니다. 다만 노드는 메모리 여러 군데에 저장되며 노드 안에 다음 노드의 정보를 기입하여 다음 노드를 불러올 수 있는 식으로 데이터의 저장 및 활용이 가능해지는 것이다. 이러한 노드는 링크드 리스트뿐만 아니라 여러 가지 자료구조를 구현할 때 사용이 된다.

 

링크드 리스트

 

링크드 리스트의 경우 이제 node의 next부분에 다음에 올 노드의 정보를 저장하면서 이어진다. 이때 제일 첫번째 오는 노드를 head라고 칭한다. 기본적으로 구현이 되는 메서드는 append / print_al / get_node /  add_node /  delete_node가 존재한다. 해당 메서드의 역할과 과정은 코드 안에 주석에서 설명하겠다.

 

'''
노드이다.
노드의 경우 앞에서 말한 바와 같이 데이터를 저장하는 인자와
다음 데이터를 받아오기 위한 정보가 있는 next로 구성이 되어있다.
처음 next값은 다음 노드의 정보를 원활하게 받아오기 위해 None으로 지정을 한다.
'''


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


'''
node를 이어서 만드는 링크드 리스트 자료구조이다.
'''


class LinkedList:
    # 생성자
    def __init__(self, value):
        # 연결리스트의 가장 처음에 오는 노드는 head라고 지정을 한다.
        self.head = Node(value)

    # ------------------------------------------------------------------------------------------------------------------

    # 1. append : 추가하고자 하는 값을 받아와서 제일 마지막 노드에 넣어 연결을 하는 메서드
    # 해당 메서드의 경우 시간복잡도는 o(n)이다. while을 통해 현재 리스트 안에 저장된 데이터의 갯수에 따라 반복문을 진행하기 때문이다.
    def append(self, value):
        # cur을 선언해준다. cur의 경우 head, 즉 처음부터 시작을 한다
        cur = self.head

        # cur의 next가 None이 아닐 때까지 반복을 하며 cur의 경우 반복분이 진행될 때마다 다음 cur로 넘어가게 된다.
        while cur.next is not None:
            cur = cur.next
        # 만약 반복문이 종료가 되면 해당 경우에는 현재 가지고 있는 cur의 next가 None이라는 의미이며
        # 이 경우 Node를 새로 선언하고 해당 노드를 cur의 next로 지정을 해준다.
        cur.next = Node(value)

    # ------------------------------------------------------------------------------------------------------------------

    # 2. print_all : 해당 리스트의 데이터 값을 모두 보여주는 메서드
    # 해당 메서드의 경우 시간복잡도는 o(n)이다. while을 통해 현재 리스트 안에 저장된 데이터의 갯수에 따라 반복문을 진행하기 때문이다.
    def print_all(self):
        # cur을 선언하고 이는 현재 cur의 head이다.
        cur = self.head
        # 현재 cur이 아무것도 존재하지 않을 때 까지만 반복을 한다.
        while cur is not None:
            # cur.data를 출력하고, cur을 cur의 next로 선언한다
            print(cur.data)
            cur = cur.next

    # ------------------------------------------------------------------------------------------------------------------

    # 3. get_node : n번째 리스트의 값을 반환하는 메서드
    # 해당 메서드의 경우 시간복잡도는 o(index)이다. while을 통해 현재 리스트 탐색의 갯수에 따라 반복문을 진행하기 때문이다.
    def get_node(self, index):
        node = self.head
        # index와 비교를 위해 count 선언
        count = 0
        while count < index:  # 해당 반복문은 count가 index보다 작을 때까지만 반복을 하며
            node = node.next  # 노드의 상태를 반복문이 진행할 때마다 다음 노드를 가져온다
            count += 1
        return node  # index값에 맞는 노드를 리턴하여 보여준다

    # ------------------------------------------------------------------------------------------------------------------

    # 4. add_node : 원하는 자리에 원하는 값을 넣는 메서드
    def add_node(self, index, value):
        new_node = Node(value) # 새로운 노드 생성
        # 다만 new_node가 원하는 index가 처음인 경우
        if index == 0:
            # new node의 next를 현재 head로 지정한다. 그리고 다음 현재 head값을 new_node로 지정한다
            new_node.next = self.head
            self.head = new_node
            return

        # 원하는 index에 해당 노드를 넣어 값을 지정하고 보관하고 싶은 경우
        # index - 1 번째의 노드를 가져오고 해당 노드의 next에 새로 생성한 new_node를 넣어줘야 제 위치를 찾아갈수 있다.
        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

    # ------------------------------------------------------------------------------------------------------------------

    # 5. delete_node : 인덱스를 입력받고 그 인덱스의 노드를 제거하는 메서드
    def delete_node(self, index):
        # 만약 지우고자 하는 index가 0이라면
        if index == 0:
            # 현재 해드는 현재 해드의 다음으로 덮어씌워진다
            self.head = self.head.next
        # index -1의 노드를 get_node 메서드를 통해 가져온다
        node = self.get_node(index - 1)
        # 그리고 나서 그 노드의 다음의 다음 노드를 가져오는 정보를 현재 노드로 이어붙여준다
        node.next = node.next.next

 

 

 

파이썬의 리스트

 

 파이썬에서 공란의 리스트를 만들고 간단하게 메서드를 살펴보면 많은 메서드들이 선언되어있다. 

 

실제로 리스트를 사용할 때 리스트에 구현된 메서드이기에 당연하게도 리스트의 경우 연결 리스트로 구현이 된줄 알았었다. 그런데 오늘 파이썬의 리스트는 동적 배열이란 것을 사용하여 만들어졌다고 해서 한 번 찾아보게 되었다.

 

정적 배열이란?

• 정해진 크기의 메모리 공간을 할당하여 사용
• 할당받은 메모리에 같은 타입의 데이터 자료형만 입력 가능
  • int는 int끼리, str은 str끼리
• 한번 크기가 정해지면 크기를 수정할 수는 없다.
  • 예전에 자바로 알고리즘 문제를 풀었을 때는 배열의 크기를 입력받아 크기를 입력값에 따라 변하게 하면서 진행하였다.

 

 

동적 배열이란?

 

• 크기 조정이 가능한 배열
  • 입력값에 따라 배열의 길이가 달라지는 동적으로 할당되는 배열이나 가변 길이 배열이 아님 
• 배열과 유사한 성능을 가지고 있지만 요소를 추가하고 제거하는 새로운 작업이 추가됨
  • 특정 인덱스에서 값 가져오기 또는 설정 - 시간 복잡도 O(1)
  • 순서대로 요소 반복 (선형 시간, 개선된 캐시 성능)
  • 배열 중간에 요소 삽입 및 삭제 (선형 시간)
  • 배열의 끝에 요소 삽입 및 삭제 (일정한 분할 상환 시간)
• 기존 배열의 비효율성을 개선하기 위해 등장

 

동적 배열 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

Dynamic array - Wikipedia