지난 포스팅에는 배열에 대한 설명을 했다.
하지만 기억이 잘 안난다면 아래의 정리를 보자.

• 파이썬에서의 배열은 리스트(List) 자료형을 사용한다.
• 리스트는 자료형이 연속적으로 들어간 하나의 집합이다.
• 리스트는 정적이 아닌 가변적인 자료형이다.
• 리스트는 동적 메모리 영역에서 할당된다.

오늘 정리할 연결 리스트는 위에서 언급한 4가지의 특징 중 특히 2번째의 특징이 다른 자료구조이다.

📘 연결 리스트 (Linked List)

연결 리스트는 다음과 같은 특징이 있다.

• 노드(데이터 + 포인터) 형태로 이루어져 있음.
• 배열과 달리 저장이 연속적이지 않음.
• 노드의 구성 요소 중 데이터 필드에는 사용자가 원하는 값이나 정보 등이 들어가고 포인터 필드에는 다음 노드로 이동하기 위한 위치 정보가 저장되어 있다.

🤔그렇다면 연결 리스트는 왜 쓸까?

가장 큰 이유는 데이터의 삽입과 삭제를 빠르게하기 위함이다.

배열의 경우, 맨 끝에서 삽입/삭제하는 경우가 아니면 최악의 경우 O(n)이라는 시간 복잡도가 나오는데
연결 리스트의 경우, 삭제할 노드의 위치를 알고 있다면 O(1)의 시간복잡도가 걸려 훨씬 삽입과 삭제에 있어 용이하다.

📘 단일 연결 리스트 (Single Linked List)

가장 먼저 단일 연결 리스트에 대해 정리해보았다.

단일 연결리스트는 데이터+다음 노드의 위치(포인터) 형태로 구조가 되어있고
아래의 그림을 메모리 영역으로 보았을 때 그려진 형태와 같이 자료가 저장/위치하게 된다.

여기서 중요한 점은 단방향 이동이라는 점이다.
A -> B -> C -> D 순으로 이동은 가능하나 포인터(next)가 가리키는 방향을 제외하곤 이동이 불가하다.

💻 Node

class Node: # 노드의 생성문 
    def __init__(self, data, next = None):
        self.data = data # 데이터 필드
        self.next = next # 포인터 필드

위의 설명과 같이 노드의 생성문이다.

Node를 호출할 때 생성자(init)을 활용해 객체를 만들어 낼 수 있도록 했고,
데이터 필드에는 필요에 따른 값이나 정보를. next 필드에는 초기값 None으로 지정해주었다.

💻 Main

class main:                      # 메인 메서드 동작 및 Head / Tail 생성문
    def __init__(self) -> None:
        self.head = None
        self.tail = None

메인 클래스에서는 객체 변수 head와 tail을 선언/초기화 해주었다.

💻 end_Insert & select_Insert

def end_insert(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

새로운 노드를 생성하여 연결 리스트의 맨 끝에 새로운 값을 삽입한다.
값이 비어있다면 객체 변수(head, tail)에 새로운 노드를 넣어 head를 정의해주게 된다.

반대로, 값(head)이 있다면 head의 next 변수 값을 초기에 한번 설정.
(이때 head.next 값은 tail을 가리키게 된다)

그리고 tail의 next 변수 값을 재설정하며, tail 변수에 새로운 노드를 할당함으로써
다음 값을 받아올 때 다시 연결리스트를 구성하도록 설정한다.

def select_insert(self, data, pick_node):
    new_node = Node(data)    # 새로운 노드 생성                
    search = self.head       # 탐색 변수를 생성하여 head노드부터 순차적으로 탐색

    while self.head is not None:
        if search.data == pick_node:
            new_node.next = search.next
            search.next = new_node
            break
        else:
            search = search.next

위의 end_Insert 메서드와 비슷하게 구성되어 있으나 탐색이 추가되어있다.

매개변수로 (self, data, pick_node)를 받도록 설정했고,
이 중에 node의 데이터 값과 pick_node(직접 찾으려는 데이터 값)를 통해 비교하고자 했다.

( data = new_node 내에 들어갈 값 또는 정보 )
( pick_node = 찾으려는 노드의 데이터 값 )

💻 select_remove

def select_remove(self, pick_node):
       prev_node = self.head                    # head값으로 초기 설정. 삭제할 노드를 찾았을 때 이전 노드의 next 값을 변경하기 위함.
       current_node = self.head.next            # head.next의 값. 이 변수를 통해 직접적인 값을 비교.

       while self.head is not None:
           if self.head.data == pick_node:      # head 값이 삭제해야할 데이터 값일 때, 실행
               self.head = None
               self.head = self.head.next
               break
           if current_node.data == pick_node:   # 직접적인 값을 비교
               prev_node.next = current_node.next
               break
           else:
               prev_node = current_node         # 다음 노드로 순차적 이동
               current_node = current_node.next

이 메서드도 select_Insert와 동일하게 탐색의 구조가 포함되어있다.

삭제하려는 값과 노드의 값을 직접적으로 비교할 때, 단순하게 이전 노드의 포인터를 변경해줘야겠다 라는 생각이 들어 이전 노드의 정보와 현재 비교하는 노드의 정보를 담은 두 개의 변수를 생성했다.

처음 if문을 들어가 head노드의 값과 찾으려는 값을 비교한 후 직접적인 값을 비교하도록 했고
이후 if문에서는 값이 일치할 때, 이전 노드의 포인터를 변경. 값이 불일치 시 다음 노드로 순차 이동하도록 구성했다.

🧐 How was it...and?

1. 배열과의 차이점?

사실 우리가 원하는 데이터를 찾고 삽입이나 삭제를 하고자 할 때, 탐색이라는 절차를 한번 거치게 된다.

이렇게 되면 삽입과 삭제에 있어서는 O(1)이었던 시간복잡도가 탐색 + (삽입 or 삭제) 라는 과정으로 변경되기 때문에 O(n)과 다를 게 없다는 생각이 들었다.

2. 다른 구현

위의 사례와 같이 직접적으로 데이터에 접근하거나 head에 값을 직접 할당해주는 방식이 아닌
더미 노드를 사용하는 구현 방법과 메서드에서 Node의 정보를 담은 return 값을 받아 다른 메서드에서 재사용하는 방식의 코드를 확인한 적이 있었다.

나름 스스로 구현해보는 것도 좋을 것 같다 싶어 Node 및 객체 변수의 기본 틀을 보고 코드를 짜보았으나 더욱 효율적인 코드가 있는 것을 확인하였다.

아직 여러 부분에서 학습이 덜 되어 있는 것 같아 스스로도 조금 아쉬움이 많이 남는 것 같다.