Linked List 1

📚 Linked List 특징

💡 Linked List 특징

• 1. Linked List는 인덱스를 가지고 있지 않다.
• 2. Linked List에 노드는 메모리에 연속적으로 저장되지 않고 사방에 흩어져서 저장된다.
• 3. Linked List에는 Head라는 변수가 있고, 이는 첫 번째 노드를 가르킨다.
• 4. Linked List에는 Tail라는 변수가 있고, 이는 마지막 노드를 가르킨다.
• 5. Linked List에 각각의 노드들은 서로 다음, 다음을 가르키게 되고, 마지막 노드는 아무것도 가리키지 않는다.

• Linked List
  
  • 메모리 상에서, Linked List 저장되어 있는 방식을 그림으로 나타낸 것.
  • 다음 그림처럼, Linked List는 다음 노드를 계속해서 가리키고 있기 때문에, 데이터를 잃지 않고 노드를 찾을 수 있다.

• List
  
  • 일반적인 배열에 메모리 저장 방식
  • 일반적인 배열은, 위 그림과 같이 연속적으로 메모리에 저장되기 때문에, 인덱스를 가질 수 있고, 각각의 인덱스를 메모리의 특정 주소로 매핑할 수 있기 때문에 접근할 수 있다.

📚 Linked List - Big O

💡 Linked List를 위해 만들 모든 메소드와 Big O

💡 1. 첫 번째 메소드 : 목록 끝에 새 노드를 추가하는 메소드

• 마지막 노드가 추가 될 노드를 가리킨다.
• 그 다음 Tail이 마지막 노드를 가리키게 됨으로, Linked List에 새로운 노드를 추가한다.
• O(1)

💡 2. 두 번째 메소드 : 목록에 마지막 노드를 삭제하는 메소드

• 마지막 노드를 제거하고, Tail을 새로 바뀔 마지막 노드에 추가해주어야 한다.
• 새로 바뀔 마지막 노드를 가리키는 포인터를 찾아야 한다.
• 그 노드를 가리키는 포인터를 찾기 위해서는 Head 부터 출발해서 해당 Linked List를 순환해야 한다.
• 순환 끝에 찾은 포인터를 Tail이 가리키도록 설정해준다.
• O(n) : 전체 리스트를 순환했기 때문

💡 3. 세 번째 메소드 : 목록 맨 앞에 새 노드를 추가하는 메소드

• 새로운 노드가 Linked List 맨 앞의 노드를 가리킨다.
• 그 다음 Head를 새로 추가된 노드를 가리키게끔 하여, Linked List에 새로운 노드를 추가한다.
• O(1)

💡 4. 네 번째 메소드 : 목록 맨 앞에 새 노드를 삭제하는 메소드

• Lined List에 두번째 노드를 새로운 Head가 가리키게끔 한다.
• 그 다음 맨 앞에 노드를 Linked List에서 삭제 해준다.
• O(1)

💡 5. 다섯 번째 메소드 : 목록 중간에 새 노드를 추가하는 메소드

• 내가 추가하고 싶은 노드를 가리키는 포인터를 찾기 위해선, 해당 Linked List를 순환하며 해당 포인터를 찾아야 한다.
• 그렇게 찾은 포인터는 추가하고 싶은 노드를 가리키도록 설정 한다.
• 새로 추가된 노드에 포인터는 그 다음번 노드를 가리키도록 설정 한다.
• O(n)

💡 5. 여섯 번째 메소드 : 목록 중간에 노드를 삭제하는 메소드

• Linked List를 순환하여 내가 삭제하고 싶은 노드를 찾는다.
• 찾은 노드 이전 노드의 포인터로 하여금, 찾은 노드의 포인터가 가리키고 있는 노드를 가리키도록 수정해준다.
• 그리고 찾은 노드를 제거해준다.
• O(n)

📚 Linked List Vs List