2주차 링크드리스트

2주차 링크드리스트

Array vs LinkedList

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

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

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

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

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이라는 변수에 this.head를 넣어준다.

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

# 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 = Node(data)

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

#append와 마친가지로 cur에 head의 값을 넣어주고 cur = self.head #cur이 not이 아니면 while문을 탄다. while cur is not None: #cur의 data를 출력한다. print(cur.data) #cur이 이제 cur의 next를 참조하도록 하자. cur = cur.next #cur.next가 있다면 다시 while문을 탈 것이고 None이라면 여기서 탈출할 것이다.

반응형

from http://taehyeki.tistory.com/128 by ccl(A) rewrite - 2021-12-20 23:00:43