연결 리스트 - 한방향 연결 리스트(Singly Linked List)

1. 한방향 연결 리스트

배열은 메모리상에 줄줄이 붙어 있는 느낌이다.
연결 리스트는 노드들이 주소로 이어진 체인이라고 보면 된다.

예를 들어:

[10 | • ] -> [20 | • ] -> [30 | None]   여기서 각 [] 칸이 노드(Node)이다.

앞칸 : 데이터
뒤칸 : 다음 노드를 가리키는 주소(next)

즉, 한방향 연결 리스트는 앞에서 뒤로만 따라갈 수 있는 줄줄이 연결된 구조이다.

한방향 연결 리스트 head와 tail이 존재하는것을 볼 수 있다.

 

2. 왜 연결 리스트를 쓸까?

배열은 중간에 삽입/삭제할 때 뒤 원소들을 밀거나 당겨야한다. 그런데 연결 리스트는 그게 아니라 앞 노드의 next, 새 노드의 next
이 두 개만 잘 바꾸면 된다. 따라서 연결 리스트는 삽입/삭제에 강하다

3. 삽입 연산 : 노드를 끼워 넣는다는 건 무슨 뜻인가?

예를 들어:
10 -> 20 -> 30

여기서 20 뒤에 25를 삽입 하고 싶다면
원래는 :
10 -> 20 -> 30
삽입 후:
10 -> 20 -> 25 -> 30
1. 새 노드 25를 만들고:
2. 25.next = 20.next
3. 20.next = 25

먼저 새 노드가 원래 뒤 노드를 가리키게 하고
그 다음 앞 노드가 새 노드를 가리키게 만든다

이 순서를 거꾸로 하면 원래 뒤쪽 연결을 잃어버릴 수 있다. 따라서 이게 삽입 연산의 제일 중요한 포인트다.

4. 왜 순서가 중요한가?

잘못해서 먼저 20.next = 25 이걸 해버리면, 원래 20이 가리키던 30 주소를 잃을 수 있다. 즉, 체인이 끊긴다.
그래서, 연결 리스트에서는 항상 이런 느낌으로 생각 해야 한다. 뒤를 먼저 살려놓고, 앞을 연결한다.

5. 맨 앞(head)에 삽입은 더 쉽다.

10 -> 20 -> 30
인데 맨 앞에 5를 넣고 싶으면

5 -> 10 -> 20 -> 30
방법은 :
new.next = head
head = new
끝. 왜 쉽냐면 앞 노드 찾는 과정이 필요 없기 때문이다.

 

한방향 연결 리스트 중간 삽입 이미지

6. 삭제 연산 : 노드를 없앤다는건 뭘까?

연결 리스트 삭제는 "그 노드를 지운다"기보다 정확히 그 노드를 건너뛰게 만든다. 라고 이해해야함
10 -> 20 -> 30
여기서 20을 삭제하면 결과는
10 -> 30
그럼 여기서 실제로 하는일은 :
10.next가 원래 20을 가리키고 있었는데
이제 30을 가리키게 바꾼다
즉 10.next = 20.next 이게 핵심

7. 삭제도 "앞 노드"가 중요함

한방향 연결 리스트는 뒤로 못간다. 따라서 20을 지우려면 20 자신만 알아서는 부족하고, 그 앞 노드인 10을 알아야 한다.
왜냐하면 연결을 바꿔야 하는 쪽은 삭제할 노드가 아니라 그 앞 노드의 next 이기 때문이다.

삭제 전:
10 -> 20 -> 30

삭제 후:
10 ---------> 30

즉, 20을 없애는 게 아니라 10이 20를 건너뛰게 만드는 것이 삭제다.

8. 맨 앞(head) 삭제는 예외이다.

만약 맨 앞 노드 10을 삭제하면
10 -> 20 -> 30
삭제 후 :
20 -> 30
이 경우에는 앞 노드가 없으니까  그냥 head = head.next를 하면 된다. 즉, head가 다음 노드로 이동하면 끝임

9. 삽입/삭제의 가장 중요한 포인트

"데이터를 바꾸는 거야? 주소를 바꾸는 거야?" 당연하게도 주소(next)를 바꾸는것이다.
예를 들어 20 뒤에 25 삽입할 때 20의 데이터값을 25로 바꾸는게 아니다. 새 노드를 하나 만든 다음
연결 화살표를 다시 꽂는 거다. 즉, 연결 리스트 문제는 거의 다

• 어느 노드가 앞 노드인가
• 어느 노드가 현재 노드인가
• next를 어떤 순서로 바꿔야 체인이 안 끊기는가
  이 세 가지 유형이다.

한방향 연결 리스트 delete를 표현

 

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def __len__(self):
        return self.size
    
    def pushfront(self, data):   # O(1)
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def pushback(self, data):  # O(n)
        v = Node(data)
        if len(self) == 0:
            self.head = v
        else:
            tail = self.head # 처음 시작하는곳은 head임 그래서 tail을 찾기 위해 while루프 이용
            while tail.next != None: # tail.next가 None가 아니면 tail.next가 될 때 까지 루프
                tail = tail.next
            tail.next = v
        self.size += 1 #if가 참이든 아니던 상관없이 size 1을 늘려준다.

    def popfront(self):  # O(1)
        if len(self) == 0:
            return None
        else : #하나 이상 노드 존재 시 
            x = self.head
            data = x.data
            self.head = x.next
            self.size -= 1
            del x
            return data
        
    def popback(self):  # O(n)
        if len(self) == 0:
            return None        
            #running technique
        prev, tail = None, self.head
        while tail.next != None:
            prev = tail #원래 prev가 있던곳을 tail 되게하고
            tail = tail.next # tail은 tail.next가 되게한다.
        data = tail.data        
        if len(self) == 1:
            self.head = None
        else:
            prev.next = tail.next
        del tail
        self.size -=1
        return data
    
    def printlist(self): #리스트 전체를 보기위한 출력 메서드
        cur = self.head # self.head가 연결리스트의 첫 번째 노드이고 cur이 현재 보고 있는 노드
        while cur != None: # 마지막 노드가 None이 될때 끝
            print(cur.data, end=" -> ") # 현재 cur 가 x 노드를 가리키고 있으면 x -> 출력 end=" -> " 는 줄바꿈 방지
            cur = cur.next # 현재 노드 출력 후, 다음 노드로 이동
        print("None") # 연결 끝 

    def search(self, data): #data값의 노드를 리턴, 없으면 None 리턴 O(n)
        v = self.head #맨 앞부터 본다.
        while v != None: #None이 아닐때 까지 반복
            if v.data == data: # 찾고싶은값이 x이면 해당 x를 찾을떄까지 확인 
                return v # 위에서 x값을 찾았다면 반환
            v = v.next #아니면 v가 v.next가되어서 다음 노드로 이동
        return None # or return v(얘는 어차피 None이므로)
    
    def __iter__(self): #스페셜 메소드 제너레이터(generator) for문을 사용하기 위한 메서드
        v = self.head
        while v != None:
            yield v #이것이 핵심 이게 있어야 제너레이터임 여기서 yield는 값을 호출한 쪽으로 넘겨주고, 함수의 실행 상태를 저장한 채 잠시 멈춘다.
            v = v.next 
        #return for _ in 루프를 사용할 수 있는데. 이게 이제 for문을 반복하다가 파이썬이 내부적으로 stopiterator를 만나면 자동으로 반복을 나옴

 

단방향 연결 리스트를 표현했다. 
스페셜 메서드 iter를 배웠고, 이것을 이용하여 for문을 사용 할 수 있는것을 배웠다.

위 의 코드를 이용하여 아래 문제를 풀면 주석과 같다.

#--- 문제 풀이 ---
L = SinglyLinkedList()

L.pushfront(10)   # 10 -> None
L.pushfront(20)   # 20 -> 10 -> None
L.pushback(30)    # 20 -> 10 -> 30 -> None
L.pushfront(40)   # 40 -> 20 -> 10 -> 30 -> None
L.popfront()      # 20 -> 10 -> 30 -> None
L.popback()       # 20 -> 10 -> None
L.printlist()     # 20 -> 10 -> None 최종 list

#--- search 메서드 이용 ---
node = L.search(90)
if node != None:
    print("찾음:", node.data)
else:
    print("없음")

 

Search 메서드의 경우에는 node를 찾았을때는 return v 즉, 그 노드 자체를 참조할 수 있게 돌려줍니다.

따라서, 그 노드의 data확인, data수정, next확인, next변경 같은 작업이 가능해지죠, 이걸 Python에서는 보통 객체 참조를 이용한다 라고 합니다. 따라서 print(node)를 하게된다면 Node 객체 자체를 반환해서 해당 노드의 메모리 주소값을 보여주게 되므로
print(node.data)으로 출력하게 합니다.