Array와 Linked List

Array

  • 크기가 정해져있는 공간
  • 배열은 같은 형의 구성 요소가 직선 모양으로 연속하여 줄지어 있는 단순한 자료구조
  • 탐색시간 O(0) - 접근이 빠름 ex) a[0]
  • 단점 : 수정, 삭제가 어렵다

Linked List

  • 노드 : data와 next를 가지고 있음
  • Linked List는 위의 노드들이 연결되어 있는 형태
    Linked List : head Node[data-next]-Node[data-next]-Node[data-next]-...
  • 다음 노드의 정보를 가지고 있는 노드들이 연결되어 있는 형태
  • 탐색시간 : O(N)
  • 삽입, 삭제가 편하다

구현

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next
               

    def get_node(self, index):
        node = self.head
        count = 0
        while count<index :
            node = node.next
            count += 1
        return node
    def add_node(self,index,value):
        new_node = Node(value)
        if index ==0 :
            new_node.next = self.head
            self.head = new_node
            return            
        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

좋은 웹페이지 즐겨찾기