(자료구조) 연결 리스트를 알아봅시다. - I am yumida

제가 요즘 코딩 테스트를 준비하면서 자료 구조도 함께 공부하고 있는데요. 연결 리스트라는 큰 난관에 부딪혀서 어려워하고 있습니다. 따라서 저처럼 연결 리스트를 어려워하시는 분들을 위해 게시물을 만들었습니다.

 

게시물을 읽으신 모든 분들....... 연결 리스트 타파합시다. 화이팅입니다.

 

'Do it 자료구조' 책의 도움을 많이 받았습니다. 감사합니다.

 

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=246435695 

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편

 

 

오늘의 게시물은 아래 항목으로 나눠집니다.

 

1. 연결 리스트란?

2. 머리 노드와 꼬리 노드란?

3. 파이썬으로 연결 리스트를 만들어보기 

 

그럼 시작하겠습니다.

 

1. 연결 리스트란?

 

연결 리스트는 데이터를 사슬처럼 연결한 구조입니다. 연결 리스트에서는 각 원소들을 노드라고 부릅니다. 이 노드는 data와 next, pointer 로 구성됩니다. data는 노드의 data, next와 pointer는 뒤쪽 노드(바로 옆에 있는 노드)에 대한 참조를 의미합니다. [그림 1]은 연결 리스트의 기본적인 구조입니다. (연결 리스트 1->3->4 를 나타냈습니다) 

 

[그림 1] 연결 리스트의 구조

 

[그림 1]을 설명하자면 node A의 뒤쪽 포인터 next 가 node B를 참조하고 node B의 뒤쪽 포인터 next 가 node C를 참조합니다. 그럼 node C의 뒤쪽 포인터는 무엇을 참조할까요? 더이상 참조하는 대상이 없기 때문에 None을 참조합니다.

 

만약에 node C를 삭제하고 싶다면 어떻게 할가요? 우선 node A부터 node B까지 이동한 후 node B의 뒤쪽 포인터가 None을 참조하면 됩니다. 연결 리스트에서 특정 노드를 찾을 때 또는 특정 노드에 다가가고 싶을 때 처음 노드부터 연결된 순서로 이동해야 됩니다. 

 

2. 머리 노드와 꼬리 노드란?

 

리스트와 다르게 연결 리스트에는 머리 노드가 존재합니다. 머리 노드는 처음 시작하는 노드입니다.

 

[그림 1]에서는 머리 노드가 node A이겠죠? 이 머리 노드는 또다른 존재 head에 의해서 선택받은 자입니다.

head는 머리 노드를 참조하는 존재입니다.  [그림 1]에서 head는 node A를 참조했으므로 node A가 연결 리스트의 머리 노드입니다.

 

만약 머리 노드를 새로운 노드 node G로 변경하려면 어떻게 할까요? head가 node G를 참조하여 '얘가 머리 노드이다'라고 선언하면 됩니다. 그리고 node G의 뒤쪽 포인터는 기존의 머리 노드 node A를 참조합니다.

 

[그림 1] 연결 리스트의 구조

 

머리 노드가 있으면 꼬리 노드도 있겠죠? node C의 뒤쪽 포인터는 더이상 참조하는 대상이 없기 때문에 None을 참조합니다. 이렇게 뒤쪽 포인터가 더이상 참조하는 게 없는 경우, 해당 노드를 '꼬리 노드' 라고 합니다.

 

3. 파이썬으로 연결 리스트를 만들어보기 

 

이번에는 연결 리스트를 파이썬에 입력해봅시다.

우선 코드에 대한 설명을 한 후, 1->3->4->5를 입력해보겠습니다.

이후 연결 리스트를 구현하는 다른 방법을 알려드리고 마치겠습니다.

 

코드 설명

 

from __future__ import annotations
from typing import Any, Type

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

 

#첫 번째로 head, data, next, current 초기값을 정의합니다.     
    def __init__(self, data:Any=None, next: Node=None):
        #초기화
        self.data=data #데이터에 대한 참조
        self.next=next  #뒤쪽 노드에 대한 참조
        self.head=None #머리 노드에 대한 참조
        self.current=None

        #현재 주목하고 있는 노드에 대한 참조(리스트에서 노드를 검색하여, 그 노드를 주목한 직후에 노드를 삭제하는 등의 용도로 사용됩니다.)
        

#두 번째로 머리 노드를 생성합니다. [그림 2]
    def add_first(self, data:Any)->None:
        ptr=self.head

        #삽입하기 전의 머리 노드, 저희는 머리 노드를 생성하는 단계이니 None이겠죠?
        self.head=self.current=Node(data,ptr)

         #삽입할 노드 node A를 Node(data,ptr)로 생성합니다.

         #해당 노드의 데이터가 data가 되고, 해당 노드의 뒤쪽 포인터가 참조하는 곳은 ptr이 됩니다.  

        return self.head

 

[그림 2] 머리 노드 생성 과정

        
#세 번째로 만들어진 연결 리스트의 끝 노드에 새로운 노드를 삽입합니다. [그림 3]

    def add_last(self, data=Any):
        if self.head is None:

            self.add_first(data)

            #만약에 head가 없는 경우, 앞에서 정의한 add_first함수로 head를 생성합니다.

        else:
            ptr=self.head

            #While문을 이용해서 꼬리 노드를 찾습니다.
            while ptr.next is not None:
                ptr=ptr.next

               #연결 리스트에서 특정 노드를 찾을 때 무조건 머리 노드부터 하나씩 지나면서 이동합니다.

            ptr.next=self.current=Node(data,None)
            #꼬리 노드를 찾았으면 꼬리 노드 옆에 새로운 node D Node(data,None)를 추가합니다. 

            #Node(data,None)에서 새로운 node D의 뒤쪽 포인터가 참조하는 것이 None인 이유는

            #node D가 곧 꼬리 노드가 되기 때문입니다.

            return ptr

 

[그림 3] node D 추가 과정

 

구현하기

A=Node() #클래스 할당
A.add_first(1) #머리 노드 지정 (node A)
A.add_last(3) #꼬리 노드에 새로운 노드 추가 (node B)
A.add_last(4) #꼬리 노드에 새로운 노드 추가 (node C)
A.add_last(5) #꼬리 노드에 새로운 노드 추가 (node D)

 

결과 확인하기 (긴가민가 합니다. 틀리면 바로 댓글 주세요!)

 

[그림 4] 노드 생성 후 결과

 

[그림 4]는 앞의 코드 구현한 후 object 항목에서 가져왔습니다. 1->3->4->5가 잘 들어갔는지 확인해보겠습니다.

 

- 우선 path의 A.head를 봅시다. A.head는 머리 노드 node A를 참조합니다. 따라서 A.head의 data (A.head.data)는 node A의 데이터 1 입니다.  

 

- path의 A.head.next 를 봅시다. A.head.next는 머리 노드 node A의 뒤쪽 포인터가 참조하는 노드입니다. [그림 3]에 따르면 node B겠죠? 마찬가지로 A.head.next의 data (A.head.next.data)는 node B의 데이터 3 입니다.

 

- path의 A.head.next.next 를 봅시다. A.head.next.next는 node B의 뒤쪽 포인터가 참조하는 노드입니다. [그림 3]에 따르면 node C겠죠? A.head.next.next의 data (A.head.next.next.data)는 node C의 데이터 4 입니다.

 

- path의 A.head.next.next.next 를 봅시다. A.head.next.next.next는 node C의 뒤쪽 포인터가 참조하는 노드입니다. [그림 3]에 따르면 node D겠죠? A.head.next.next.next의 data (A.head.next.next.next.data)는 node D의 데이터 5 입니다.

 

**연결 리스트를 구현하는 방법이 하나 더 있습니다.

https://lsjsj92.tistory.com/461 블로그에서 더 간단한 방법을 찾았습니다. 

근데 코드를 갖고오는게 저작권 침해 같고 걱정돼서 링크만 올렸습니다. 여기서 더 쉽게 구현할 수 있습니다!!

 

여러분, 사실 이 게시물은 빅픽처입니다. 다음 게시물에서는 리트코드 문제 풀이를 할건데요. 이 문제를 풀기 위해서 연결 리스트 개념이 꼭 필요하답니다. https://leetcode.com/problems/merge-k-sorted-lists/

Merge k Sorted Lists - LeetCode

그럼 곧 봐요!!