Array, Linked List

Array

서로 연관된 데이터들을 메모리에 연속적이게 저장하는 자료구조

배열은 처음에 크기를 선언해야하기 때문에 고정된 저장 공간을 가진다.

장단점

• 장점 : index를 알고 있으면 데이터를 조회하는데 O(1)의 시간만에 찾을 수 있다.
• 단점 : 선언시에 고정된 크기를 정해야하고 중간 원소를 삽입 삭제시에 shift 및 메모리 재할당이 일어나서 느림

시간 복잡도

Operation	Time
access (random)	O(n)
append ( capacity > size )	O(1)
delete ( last )	O(1)
insertion	O(n)
deletion	O(n)
search	O(n)

---

Linked List

• data
• address ( next node의 주소 )

Linked List는 data 와 다음 노드를 가르키는 address를 저장 하는 Node로 이어진 자료구조

address 가 다음 노드를 가르키기 때문에 논리적으로 연결되어 있음

( 배열처럼 물리적으로 메모리에 연속되어 저장되지 않고 비연속적으로 저장 됨 )

struct Node{
	int data;
	Node* next;

	Node(int d, Node* node){
		data = d;
		next = node;
	}
};

시간 복잡도

Operation	Time
access	O(n)
search	O(n)
insert	O(1)
delete	O(1)

삽입 삭제 시 address의 주소 값만 변경해주면 되기 때문에 빈번한 데이터의 삽입 삭제가 이루어지는 상황에서 사용하면 좋은 자료구조

( 반면, 데이터의 조회가 잦은 경우 배열을 이용하는게 좋음 )

장단점

• 장점 : runtime에 동적으로 사이즈를 변경하기 좋다.
  배열의 경우 선언한 길이 만큼 고정되어 있고 사용하지 않는 공간은 메모리 낭비가 일어나지만, Linked list의 경우 runtime에 자유롭게 삽입, 삭제가 가능해서 필요한 만큼 메모리를 할당한다. ( Heap공간에 할당되기 때문에 Dynamic memory allocation이라고 함 )
• 단점 : 데이터의 조회하려면 모든 노드를 순회해야 하므로 조회가 잦은 상황에서는 느리다.

Linked List Opreation

1. Travel
   노드의 데이터를 출력하고 다음 노드로 넘어가는 예
   노드의 끝 nullptr까지 순회하면 됨

    Node* node = head;
    while(node != nullptr){
    	cout << node->val << "-->";
    	node = node->next;
    }
    ```
    

2. Insert ( Begin )
   맨 앞에 노드를 넣으려면 단순히 새로운 노드를 생성하고 새로운 노드의 next address 로 head 를 가르키게 한 뒤 head 를 newNode로 변경시켜주면 됨

    Node* newNode = new Node(4, nullptr);
    newNode->next = head;
    head = newNode;
    ```
    

3. Insert ( End )
   Linked List 마지막 노드가 가르키는 주소를 newNode로 지정해주면 됨

    Node* newNode = new Node(4, nullptr);
    Node* tmp = head;
    while(tmp->next){
    	tmp = tmp->next; // 노드를 맨 마지막까지 이동
    }
    tmp->next = newNode;
    ```
    

4. Delete ( Begin )

    Node* tmp = head;
    head = head->next; // 맨 앞 요소를 옮겨주면 됨
    delete tmp;

5. Delete ( End )

    Node* tmp = head;
    while(tmp){
    	tmp = tmp->next;
    }
    delete tmp;

---

Memory 할당 방식의 차이

Array : Compile시에 고정된 크기의 메모리 할당이 이루어짐 ( Static Memory Allocation )
Linked List : Runtime에 새로운 Node를 추가할 때 마다 메모리가 할당 됨 ( Dynamic Memory Allocation )

잦은 랜덤 access와 데이터 조회에는 Array를 사용하는게 좋고
잦은 데이터의 삽입과 삭제가 일어나는 경우에는 Linked List를 사용하는게 좋다.