Udemy Computer Science 101 : Master the Theory Behind Programming 정리

Section 4 : LinkedList

Nodes

• Sequence of nodes that contain two fields(data & Next)
• 각 각의 노드가 데이터와 포인터(next 즉 다음 데이터)를 가지는 방식으로 데이터를 저장하는 자료구조이다.

Singly Linked List

• expansion 이나 doubling없이 데이터를 추가할 수 있게 만들어져있다.
• 데이터를 효율적으로 쓸 수있도록 하는 장점이 있다.
• 마지막 노드가 null을 point 한다면 그 노드가 끝이라는 의미이므로 새로운 node를추가할때 null 을 point하는 노드를 찾아서 추가하려고 하는 노드의 pointer를 새로운 노드로 point하도록 만들수 있다.
• 데이터를 삭제하려면?
  - Array라면 원하는 index로 가서 삭제하는 식의 다양한 방법으로 가능하지만 linked list 는 단순하게 중간 노드를 삭제할 수 없다.
  - 예를 들어 삭제하려고 하는 node를 포인트하던 node가 삭제하려는 node의 다음 node를 point하게 만들어야 한다.
  
  

Linked List Run Times

• array와 linked list의 run times를 비교해 보자면?

1. Insert(Random)

   • Array: O(n)
   • Linked list : O(n)

2. Insert(Front)

   • Array: O(n)
   • Linked list : O(1)

3. Insert(Back)

   • Array: O(1)
   • Linked list : O(n)

   Array는 insert back이 쉽고 insert front 은 linkedlist 보다 복잡하다. 이런 특성을 사용해서, 데이터의 앞을 추가해줘야 하는 구조라면 linkedlist를 뒤를 추가해야한다면 array를 사용하는것이 데이터 효율화에 도움이 되겠다.

4. Delete(front)

   • Array: O(n)
   • Linked list : O(1)

5. Delete(back)

   • Array: O(1)
   • Linked list : O(n)

   Delete front또한 linkedlist가 쉽고 delete back 은 array가 더 간단하다, 데이터의 앞을 삭제해야 하는 구조라면 linkedlist를 뒤를 삭제해야한다면 array를 사용하는것이 데이터 효율화에 도움이 되겠다.

6. Search(unsorted)

   • Array: O(n)
   • Linked list : O(n)

7. Search(sorted)

   • Array: Log(n)
   • Linked list : O(n)
     array의 경우 사이즈가 커질수록 계속해서 메모리를 할당해야하므로, 커질수록 메모리 부담이 커진다. linked list의 경우 계속 메모리를 할당해야할 필요는 없다. ( 시간이 많이걸릴뿐) 시간을 써서 메모리를 절약할수 있다는 장점도 있음!