Python으로 Linked List 간단히 구현하기

링크드 리스트

• Abstract Data Type
• 노드가 포함하는 내용과 다른 노드에 대한 link에 대한 정보를 포함하는 노드의 집합
• 단일 방향을 가지는 singly linked list & 양방향을 가지는 doubly linked list
• 링크드 리스트의 장점 
  • array 혹은 list에 비해 linked list의 장점은 다른 모든 items의 index를 변경할 필요없이 요소를 쉽게 삽입 및 제거할 수 있음
  • linked list를 저장하기 위해 사용되는 메모리를 재구성할 필요가 없음. 왜냐하면 데이터를 연속적으로 저장할 필요가 없기 때문

linked list는 다음과 같은 경우 유용함

• 다른 items 사이에 items을 쉽게 삽입하려는 경우
• 전체 collection 크기를 모르는 경우
• items을 찾을 때 random access가 필요하지 않음
• 데이터 저장을 위한 메모리 사용량 걱정이 없음

Python으로 구현하기 위해 아래와 같은 methods 필요

• insert(): linked list에 item 추가
• find(): linked list에서 item 찾기
• remove(): 주어진 값으로 주어진 item 제거
• is_empty(): linked list가 비어 있는지 여부를 반환
• get_count(): linked list의 items의 개수 반환

linked list를 구현하기 전에 node 클래스를 구성해야 한다. linked list 내의 각 item은 원하는 정보를 포함할 수 있고 다음 item을 식별하는 별도의 객체이다. 즉, 포함된 정보를 가리키거나 식별하는 속성이 있어야 하며 linked list의 다음 node를 가리키는 속성 또한 있어야 한다. 이를 위해, node가 포함하는 데이터와 다음 node를 모두 추출할 수 있는 동작을 추가하고 이러한 속성을 설정하거나 조정할 수 있어야 한다. 다음과 같이 구현할 수 있다.

위 코드에서 val은 node가 가지는 데이터이고 next는 linked list에서 다음 node를 가리키는 데이터이다. next를 None으로 설정하는 이유는 주어진 next node가 없기 때문이다. 그런 다음 현재 val과 next를 출력하는 & 변경할 수 있는 메소드를 추가한다.

 

여기서는 singly linked list에 초점을 맞춘다.

 

가장 처음으로 할 것은 linked list가 생성될 때마다 호출될 생성자를 생성하는 것이다. 이 경우 두 가지 속성으로 시작한다.

• head: linked list의 첫 번째 노드
• count: linked list의 노드 수

먼저 비어 있는 head를 생성하여 빈 linked list로 시작한다. 이는 item을 처음 추가할 때 head가 있는지 확인할 필요가 없다는 것을 의미한다. 또한 item을 추가하거나 뺄 수 있도록 count 속성을 추가한다.

 

linked list에서 중요한 메소드는 list 자체에 items 혹은 nodes를 추가할 수 있다는 것이다. 지금은 linked list의 head에 items을 추가하는 것에 초점을 맞춘다.

먼저 새 node를 인스턴스화하고 데이터를 새 node에 할당하고 새 node의 다음 node를 list의 현재 head로 설정한 다음 linked list의 head를 새 node로 설정하면 된다.

linked list에서 데이터를 찾기 위해 값으로 검색하는 방법에 초점을 맞춘다. linked list를 반복해 우리가 찾는 값과 node의 데이터가 일치하는지 확안한다. 즉, 최악의 시나리오에서는 linked list 내의 모든 items을 반복해야 하므로 시간 복잡도가 O(n)이 된다. item을 찾으면 해당 노드를 반환하거나 없는 경우 None을 반환하도록 한다.

항목을 삭제하는 메소드를 구현하기 위해 특정 값을 가진 item을 제거하는 데 중점을 둔다. linked list에서 item을 제거하는 것과 일반 list에서 제거하는 것의 주요 차이점은 linked list에서 node가 여전히 어딘가에 존재할 수 있다는 것이다. 이전 node의 포인터를 해당 node에서 다은 node로 변경한다. 이렇게 하면 제거된 node 이후의 모든 항목이 index를 변경해야 하는 것이 아니라 nodes 간의 연결만 변경하면 되므로 일반 list에 비해 linked list에서 item을 제거하는 것이 상대적으로 쉽다.

linked list의 길이를 반환하는 메소드는 간단하다. 

linked list가 비어 있는지 확인하기 위해 count 속성을 가져오고 이것이 0인지 여부를 확인하는 방식으로 수행한다. 그러나 간단히 head 속성이 비어 있지 않은지 여부를 확인해 linked list가 비어 있는지 여부를 쉽게 확인할 수 있다.

아래와 같은 기능을 추가할 수 있음

• deleteAt(index): 주어진 인덱스에서 항목 삭제
• findAt(index): 주어진 인덱스에서 항목 찾기
• insertAt(index): 주어진 인덱스에 항목 삽입

이는 또한 doubly linked list로 확장될 수 있다.

 

단순히 linked list를 생성하면 메모리를 재구성할 필요가 없으므로 item을 쉽게 insertion or removal 할 수 있으며 item을 메모리에 연속적으로 저장할 필요가 없다. 그러나 non-random access의 단점과 items 조회가 어렵다는 단점이 존재한다.

 

참고

아래 사이트를 공부한 글 입니다.

https://towardsdatascience.com/a-complete-guide-to-linked-lists-in-python-c52b6cb005

A Complete Guide to Linked Lists in Python