[자료구조] 연결리스트(리스트 변환, 뒤집기) by 파이썬

연결리스트는 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.

 

특징

- 동적으로 새로운 노드를 삽입하거나 삭제하기 간편

- 배열과 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수시간에 접근할 수 없다. 즉 탐색에 O(n)이 소요. 반면 시작 또는 끝 지점에 아이템을 추가/삭제/추출하는 작업은 O(1)에 가능

 

 

유용하게 쓰일 코드 스니펫들을 작성해보았다.

 

< 파이썬에서 연결리스트 클래스 만들기>

Class ListNode():
    def __init__(self, val=0, next =None):
        self.val = val
        self.next = next

 

<연결리스트 <--> 리스트>

# linkedList --> List
def nodeToList(head):
    lst = []
    while head:
        lst.append(head.val)
        head = head.next
    return lst


# List --> linkedList
def listToNode(lst):
    head = None
    while lst:
        head = ListNode(lst.pop(), head)
    return head

<연결리스트 뒤집기 두가지 방법>

def reverse(self,head:ListNode) ->ListNode:
    prev = None
    while head:
        next, head.next = head.next, prev
        prev, head = head, next
    return prev

def reverse(self,head:ListNode) ->ListNode:
    prev = None
    while head:
        prev = ListNode(head.val, prev)
        head = head.next
    return prev