[알고리즘] Python으로 LinkedList 구현하기

LinkedList = value + next address

 

python 으로 구현한 LinkedList 주석 참조

(나중에 정리해서 올릴 예정 . .)

# 노드 : value + next address

class Node:
    def __init__(self, value = 0, next = None): # 아무 값도 없을 때 초기화
        self.value = value # 객체 생성시 초기화
        self.next = next

# LinkedList는 head를 가지고 있어야함 (맨처음에 가르키는것 = head)
class LinkedList(object):
    def __init__(self):
        self.head = None # 처음 생성시 head == None
    def append(self, value): # append 구현 -> 현재 시간 복잡도 O(n)
        # new_node = Node(value)
        # self.head = new_node -> 다음 노드가 또 다시 head가 되기 때문에
        new_node = Node(value) # 생성 후
        if self.head is None: # 처음이라면 head => new_node
            self.head = new_node
        else: # 맨 뒤의 node가 new_node를 가리켜야한다.
            current = self.head # head에서 출발
            while(current.next): # 다음 노드가 없을(None) 때까지
                current = current.next
            current.next = new_node

    # 특정 위치(idx)에 있는 값 가져오는 method
    def get(self, idx):
        # head에 접근
        current = self.head
        # 원하는 인덱스(idx)로 이동
        for _ in range(idx): # --> 시간 복잡도 : O(n)
            current = current.next
        return current.value # 값 리턴

    def insert(self, idx, value): # idx에 value 추가하기
        new_node = Node(value) # 새 노드 생성
        #idx가 0일 때는 head = new_node의 다음
        if idx == 0:
            new_node.next = self.head
        else:
            current = self.head
            for _ in range(idx-1):
                current = current.next
            new_node.next = current.next
            current.next = new_node

    def remove(self, idx):
        if idx == 0:
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(idx-1):
                current = current.next # 삭제되는 idx 이전까지 current 설정
                current.next = current.next.next # 이전 idx가 다음 다음 노드를 가리키도록 설정

###### 확인 ######
ll = LinkedList() # head 생성
ll.append(1) # head 첫번째 노드를 가리킴
ll.append(2) # 1 -> 2
ll.append(3)
# ll.append(4)
ll.insert(3, 9)
print(ll.get(0))
print(ll.get(1))
print(ll.get(2))
print(ll.get(3))
ll.remove(2)
print(ll.get(0))
print(ll.get(1))
print(ll.get(2))
# print(ll.get(3))

결과 

 

tail로 append O(1)으로 구현하기

 # 시간복잡도가 O(1)인 append -> tail 활용 (맨 앞 head, 맨 뒤 tail)
    def appendtail(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node # tail과 새로운 노드 연결
            self.tail = self.tail.next # tail은 새로운 노드로 이동

 

 

https://leetcode.com/problems/design-browser-history/

prev, next 다 가지고 있는 Doubly LinkedList 구현

# 홈페이지 예제 -> 이전주소, 다음주소를 다 가지고있는 doubly LinkedList로 구현하기

# Node 생성
class ListNode(object):
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev


class BrowerHistory(object):
    def __init__(self, homepage):
        self.head = self.current = ListNode(val=homepage)

    def visit(self, url):
        self.current.next = ListNode(val=url, prev=self.current)
        self.current = self.current.next
        return None

    def back(self, steps):
        while steps > 0 and self.current.prev is not None:
            steps -= 1
            self.current = self.current.prev
        return self.current.val

    def forward(self, steps):
        while steps > 0 and self.current.next is not None:
            steps -= 1
            self.current = self.current.next
        return self.current.val


###### check ######
test = BrowerHistory("leetcode.com")
test.visit("google")
test.visit("facebook")
test.visit("youtube")
print(test.back(1))
print(test.forward(1))
test.visit("linkedin.com")
print(test.forward(2))
print(test.back(3))
test.visit("naver")
print(test.back(1))
print(test.forward(1))
print(test.forward(4))