연결리스트 (Linked List) -1

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

• Linked List
  Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조입니다. Node는 데이터 값과 Next Node의 주소값을 저장합니다. Linked List는 메모리상에서는 비연속적으로 저장이 되어있지만, 각각의 Node가 Next Node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 갖게 됩니다.

물리적 비연속, 논리적 연속

Linked List 구현

• append: O(n)

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

first = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)

first.next = second
second.next = third
third.next = fourth

get()

class LinkedList(object):
    def __init__(self):
        self.head = NOne
    def append(self, value):
        pass
    def get(self, idx):
        pass
        # head에 접근
        current = self.head
        # 원하는 index로 이동
        for _ in range(idx):
            current = current.next
        # value 반환
        return current.value

insert_at - O(n) 버전

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

class LinkedList(object):
    def __init__(self):
        self.head = None
    def append(self, value):
        pass
    def get(self, idx):
        pass
        # head에 접근
        current = self.head
        # 원하는 index로 이동
        for _ in range(idx):
            current = current.next
        # value 반환
        return current.value
        
    def insert(self, idx, value):
        # 새로운 노드 선언
        new_node = Node(value)
        if idx == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            # head에 접근
            current = self.head
            # 삽입을 원하는 index 앞까지 이동
            for _ in range(idx-1):
                current = current.next
            # new노드에 다음 노드 연결을 먼저
            new_node.next = current.next
            # 이전 노드에 new노드를 연결
            current.next = new_node

remove_at

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

class LinkedList(object):
    def __init__(self):
        self.head = None
    def append(self, value):
        pass
    def get(self, idx):
        pass
        # head에 접근
        current = self.head
        # 원하는 index로 이동
        for _ in range(idx):
            current = current.next
        # value 반환
        return current.value
        
    def insert(self, idx, value):
        # 새로운 노드 선언
        new_node = Node(value)
        if idx == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            # head에 접근
            current = self.head
            # 삽입을 원하는 index 앞까지 이동
            for _ in range(idx-1):
                current = current.next
            # new노드에 다음 노드 연결을 먼저
            new_node.next = current.next
            # 이전 노드에 new노드를 연결
            current.next = new_node
        
    def remove(self, idx):
        if idx == 0:
            self.head = self.head.next # gc가 처리
        else:
            current = self.head
            # 삭제를 원하는 이전 노드까지 이동
            for _ in range(idx-1):
                current = current.next
            # 다음 노드 주소값 변경
            current.next = current.next.next

insert_at - O(1) 버전

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

class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        # 맨 뒤의 node가 new_node를 가리킴
        else:
            self.tail.next = new_Node
            self.tail = self.tail.next