2주차 링크드리스트

Array vs LinkedList

경우	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다.	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

Python의 list도 사실 array로 구현되어 있다. append를 사용해서 새로운 배열을 만들고 있었던 것이다.

근데 내부적으로 동적 배열을 사용해서 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 설계했다고 한다.

파이썬의 배열은 링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조라고 한다!!

 

 

Linked List

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

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return

        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

Linked_List = LinkedList(3)
Linked_List.append(4)
Linked_List.append(5)
Linked_List.print_all()

 

위와 같이 구현하였다.

 

링크드 리스트란 위의 형태인데 Node로 이어져 있는 것이다. Node안에 data와 next가 각각 존재한다. 그리고 next로 다른 Node를 참조 하도록 하는 형태이다. 다음 노드를 보기 위해서는 노드의 next를 조회해서 찾아가야 한다. 

 

list의 append를 링크드 리스트에서 구현해보자 그러기 위해서는 마지막 node까지 찾아가야한다.

먼저 cur이라는 변수에 self.head를 넣어준다.

그리고 cur.next 가 None일 때 까지 계속 뒤로 넘어가야 한다. 따라서 

 

append

def append(self):
    # cur에 cur의 head값을 넣어준다. head에는 data와 next가 들어있다.
    cur = cur.head

    # cur.next의 값이 있다면 while문을 탄다. 
    while cur.next is not None:
    	# cur.next가 있다는 것이니까 이제 cur을 다음 next를 참조하도록 하자 
    	cur = cur.next
        
    # while문을 나왔다면 cur.next는 None이라는 이야기겠지?
    # 그럼 cur.next에 Node(data)를 해주자~
    cur.next = Node(data)

 

그리고 링크드 리스트의 모든 data를 출력하기 위해서도 마지막 node까지 찾아가야 한다.

 

print_all

def print_all(self):
    #append와 마친가지로 cur에 head의 값을 넣어주고
    cur = self.head

    #cur이 None이 아니면 while문을 탄다.
    while cur is not None:
    #cur의 data를 출력한다.
        print(cur.data)
    	#cur이 이제 cur의 next를 참조하도록 하자.
        cur = cur.next
    #cur.next가 있다면 다시 while문을 탈 것이고 None이라면 여기서 탈출할 것이다.

 

이번에 add_node와 delete_node에 대해서 알아보도록 하겠다.

 

add_node

add_node를 보기 위해선 먼저 get_node라는 함수가 필요하다.

 

get_node

def get_node(self, index):
    cur = self.head
    cnt = 0
    while cnt < index:
        cur = cur.next
        cnt += 1
    return cur

get_node는 index를 적어 넣으면 그 index에 해당하는 Node를 찾아서 반환해준다.

[3] → [4] →  [5] 라는 링크드 리스트가 있다고 가정할 경우

get_node(0)

get_node(2) 를 실행시켜 보겠다.

get_node(0)은 while문을 타지 않으므로 self.head에 있는 Node를 반환할 것이다.

get_node(2)는 while문을 탈 것이다

기존

[3] → [4] → [5]

cur

 

첫 번째 while문

while 0 < 2:

cur = cur.next이므로

[3] → [4] → [5]

        cur

 

두 번째 while문

while 1 < 2:

cur = cur.next이므로

[3] → [4] → [5]

                cur

3번째 와일문은 cnt가 2가되어 타지 않고 나오게 된다.

따라서 현재 cur은 2번째 인덱스에 있는 node를 가리키고 이를 반환한다.

 

이제 add_node를 설명해보겠다.

def add_node(self,index,value):
    new_node = Node(value)
    if index == 0:
        new_node.next = self.head
        self.head = new_node
        return

    node = self.get_node(index - 1)
    new_node.next = node.next
    node.next = new_node

add_node는 list의 insert와 같다. insert는 원하는 index자리에 원하는 값을 집어 넣는다.

먼저 new_node로 새로운 노드를 하나 만들어 준다.

 

그리고 index가 0일 경우에 예외처리를 해주어야 한다. [6] new_node라고 가정하겠다.

 

new_node.next = self.head 를 실행하면 아래와 같을 것이다.

  [6] new_node

  ↓

  [3] → [4] → [5]

head

 

self.head = new node 를 실행하면 아래와 같을 것이다.

  [6] → [3] → [4] → [5]

head

 

 

 

index가 0이 아닐 경우에는 1번째 index에 [6]을 넣어주겠다. index - 1 번째 node를 get_node를 통해 구하고([3])

new_node.next = node.next를 실행하면 아래와 같이 두개가 한 노드를 참조할 것이다.

[3] → [4] → [5]

   [6]↗

 

node.next = new_node를 실행하면 이렇게 된다 

[3]             [4] → [5]

     ↘[6]↗

즉

[3] → [6] → [4] → [5]와 같이 된다.

 

여기서 index -1의 node값에 넣어주는 이유는 -1을 안해주면 아래와 같이 될 것이다.

1번째에 넣어주려면 0번째의 뒤에 넣어주어야 하기때문이다.

[3] →[4] → [6] → [5]

 

delete_node

def delete_node(self, index):
    if index == 0:
        self.head = self.head.next
        return

    node = self.get_node(index - 1)
    node.next = node.next.next

delete는 생각보다 간단하다. delete 역시 0번째 index를 지우려고 하는 경우에도 예외처리를 해주어야 한다.

 

delete_node(0)의 경우 아래와 같은 상태에서

   [3] → [4] → [5] 

head

 

self.head = head.next 를 실행시키면 

 [3] → [4] → [5]

          head

 

 [4] → [5]

          head

와 같이 만들 수 있다.

 

delete_node(0)의 경우 아래와 같은 상태에서

[3] → [4] → [5]

 

node.next = node.next.next

[3]   →  [5]

      [4]↗

 

[3] →  [5] 와같이 되는 것을 확인할 수 있다.

 

두 링크드 리스트의 합구하기

def get_linked_list_sum(linked_list_1, linked_list_2):
    linked_list = [linked_list_1,linked_list_2]

    amount = 0
    for i in range(2):
        linked_list_sum = 0
        cur = linked_list[i].head
        while cur.next is not None:
            linked_list_sum += cur.data
            linked_list_sum *= 10
            cur = cur.next
        linked_list_sum += cur.data
        amount += linked_list_sum
    return amount

linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)

print(get_linked_list_sum(linked_list_1, linked_list_2))

[6] → [7] → [8]

[3] → [5] → [4]

에 해당하는 링크드 리스트를만들고 그 data들을 더하는 것이 문제인데 여기서 6+7+8 이런식으로 더하는 것이아니라

678 + 354 이렇게 더하여 1032를 반환하는 것이 문제였다.

이를 풀기 위해 먼저 노드의 데이터를 더해주고 10을 곱하면 일의 자리수가 0이되므로 온전히 더해줄 수가 있다.

ex) 678 = ((0+6) *10) → ((60 + 7) *10) → 670 + 8 → 678

 

그 과정을 while문으로 돌려서 만약 next가 cur의 next가 있다면 현재 데이터를 더하고 10을 곱해라 ! 

없다면 그냥 더해라 ! 이렇게 해서 풀었다. 선생님은 깔끔하게 함수를 다시 만들어서 풀었는데 귀찮아서 그냥 저렇게 for문을 돌렸다.