[알고리즘, 자료구조] List, LinkedList 의 이해

1 .List

•  python ->  dynamic array : 연속적
• 시간 복잡도

	Dynamic array
access / update	O(1)
insert_back	amortized O(1)
delete_back	O(1)
insert_at	O(n)
delete_at	O(n)

 

2. LinkedList, Doubly LinkedList

• LinkedList : Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조, 비연속적

• -> Node는 데이터 값(value), 주소값(next)로 구성

• 시간 복잡도

	Linked List
access / update	O(n)
insert_front	O(1)
insert_at	O(n)
insert_back	O(n) | O(1)
remove_front	O(1)
remove_at	O(n)
remove_back	O(n) | O(1)

 

<LinkedList 구현> - Python

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
        else:
            self.tail.next = new_node
            self.tail = new_node

    def get(self, idx):
        if self.head is None:
            return
        else:
            current = self.head
            for i in range(idx):
                current = self.head.next
            return current.value

    def insert_at(self, idx, value):
        new_node = Node(value)
        new_node.value = value
        current = self.head
        if idx == 0:
            self.head = new_node
            self.head.next = current
        else:
            for i in range(idx - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node

    def delete(self, idx):
        current = self.head
        if idx == 0:
            self.head = current.next
        else:
            for i in range(idx - 1):
                current = current.next
            current.next = current.next.next

[ 그림으로 표현 ]

• append

<append>

---

• get

<get>

---

• insert_at

<insert_at>

---

• delete

<delete>