Array, Linked List

Array와 Linked List

배열 (Array)

특징

 - 크기가 정해진 데이터의 공간.

 - 한번 정해지면 바꿀 수 없다.

 - 즉시 접근 가능. O(1) 내에 접근할 수 있다.

    * 다만, 인덱스를 안다는 조건 하에 접근이 효율적. 인덱스를 모르면 접근이 어려움.

 - 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다.

    * 최악의 경우 배열의 길이(N)만큼을 옮겨야 하므로 O(N)의 시간복잡도를 가진다.

 - 원소를 새로 추가하려면, 새로운 공간을 할당해야 한다.

 - Linear Search(선형검색)

 - 틀이 짜여진 초콜릿 바 같은 모양

---

링크드리스트 (Linked List)

특징

 - 크기가 정해지지 않은 데이터의 공간.

 - 특정 원소에 접근하려면 연결고리(포인터)를 따라 검색.

   * 최악의 경우 모든 노드를 탐색해야 하므로 O(N)의 시간복잡도를 가진다.

 - 원소를 중간에 삽입/삭제 하기 위해서 앞 뒤의 포인터만 변경하면 된다.

   * 원소 삽입/삭제를 상수시간 O(1)의 시간복잡도 안에 할 수 있다.

 - 열차와 비슷하게 열차칸(노드)에 데이터를 저장, 줄(포인터)로 헤드에 열차칸을 연결

---

정리

	Array	Linked List
특정 원소 조회	O(1)	O(N)
데이터 삽입/삭제	O(N)	O(1)
데이터 추가	새로운 메모리 할당	맨 뒤 노드만 추가

 - 데이터에 접근하는 경우가 빈번하다 : Array

 - 삽입과 삭제가 빈번하다 : Linked List

 

 - 파이썬 : 동적 배열을 사용. 링크드리스트 + 배열. 하이브리드

---

Linked List 구현

Node 클래스 생성

 - Node를 생성하는 기본적인 함수

class Node:
    def __init__(self, data): # data를 받아오기 위해 매개변수에 data 입력
        self.data = data      # 입력받은 데이터를 self.data에 저장
        self.next = None      # 이어진 노드가 없기 때문에 None을 넣어둠.
        
node = Node(3)  # 함수이름(입력값)으로 노드 생성.

 

LinkedList 클래스 생성

 - 리스트의 head를 생성한다.

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)  # 위의 Node 클래스를 사용해 head에 시작하는 노드의 데이터를 연결
        
linked_list = LinkedList(3)	    # 입력값 3의 노드를 헤드에 생성

 

Node 추가 (append)

 - 새로운 Node를 마지막에 생성하여 붙인다.

    def append(self, data):
        if self.head is None:       # 헤드에 노드 데이터가 없다면
            self.head = Node(data)  # 헤드에 노드를 생성
            return

        cur = self.head             # 헤드에서 시작

        while cur.next is not None:    # cur.next가 None(마지막)에 갈때까지 반복
            cur = cur.next             # 현재 cur의 다음 노드로 이동
            print("cur is ", cur.data)
        cur.next = Node(data)          # 마지막 위치에 노드 생성
        
linked_list.append(5)

 

모든 리스트 출력 (print_all)

 - 링크드리스트 내의 모든 원소를 출력한다.

    def print_all(self):
        cur = self.head        # 현재위치 헤드에서 시작
        while cur is not None: # cur의 위치가 None에 갈때까지
            print(cur.data)    # cur의 노드 데이터 출력
            cur = cur.next     # cur을 다음으로 이동
            
    linked_list.print_all()    # 모든 노드의 데이터를 순차적으로 출력

 

원소 찾기 (get_node)

 - 헤드부터 하나씩 넘기며 index 위치의 노드를 찾는다.

    def get_node(self, index):
        node = self.head        # 헤드를 node 변수에 담는다.
        count = 0
        while count < index:    # count가 index와 같아질 때까지
            node = node.next    # 다음 노드로 이동.
            count += 1          # 이동 후 카운팅
        return node
        
print(linked_list.get_node(1).data)	# 헤드의 다음 노드의 데이터를 출력

 

원소 추가 (add_node)

 - 원하는 위치에 노드를 추가한다.

    def add_node(self, index, value):     # 입력값으로 index와 value를 받아온다.
        new_node = Node(value)            # 노드를 생성
        
        if index == 0:                    # 인덱스가 0인 경우(즉, 헤드의 앞에 추가) 예외처리
            new_node.next = self.head     # 현재의 헤드를 새로운 노드의 뒤에 연결
            self.head = new_node          # 새로운 노드를 헤드로 설정
            return

        node = self.get_node(index - 1)   # 원하는 index의 앞의 노드 뒤에 추가해야 하기 때문에 -1의 위치의 노드를 get 
        next_node = node.next             # 분리할 노드를 next_node에 담아둔다.
        node.next = new_node              # 새로운 노드를 붙여준다.
        new_node.next = next_node         # 새로운 노드의 뒤에 next_node를 붙여준다.
        
linked_list.add_note(0, 3)  # index가 0이므로 헤드의 앞에 3을 추가한다.

 - (index - 1)처럼 -1 하는 코드가 있으면, 0의 경우에 대해서 예외처리를 해주어야 함. 

 

원소 삭제 (delete_node)

 - index 위치의 Node를 삭제한다.

    def delete_node(self, index):
        if index == 0:                  # 인덱스가 0일 때(즉, 헤드를 삭제하고 싶을때) 예외처리
            self.head = self.head.next  # 헤드의 다음 노드를 헤드에 담는다.
            return

        node = self.get_node(index - 1) # index의 -1번째 노드를 불러온다.
        node.next = node.next.next      # 다음 다음 노드를 다음 노드에 붙인다.
        
    linked_list.delete_node(0)   # 헤드 노드를 삭제한다.

---