Linked list

✏️ Linked list

개념

• 각 노드가 데이터와 포인터를 가지고 일렬로 연결되어 있는 방식으로 데이터를 저장
  
• header : 가장 첫번째 노드
• tail : 가장 마지막 노드

특징

• 데이터를 효율적으로 삽입/삭제/변경하기 위해 사용
• 데이터가 불연속적으로 존재하며 데이터가 서로 연결되어 있음
  • 배열 : 모든 데이터 연속적으로 존재
• 각 요소(node) = 포인터(pointer) + 데이터로 구성
  • 포인터(pointer) : 다음 노드의 위치를 가리킴

장점

• 데이터의 삽입/삭제 연산이 빠름 O(1)
  • 해당 노드가 가리키는 포인터만 변경해주면 되기 때문
  • 하지만, 탐색 과정때문에 O(N)

단점

• 데이터 접근이 느림 O(N)
  • 정해진 위치를 알지 못해 데이터를 순회해 특정 데이터를 찾아야 하기 때문

삽입 연산 - O(1)

• 새로운 요소를 추가하고자 하는 위치의 이전 요소와 다음 요소 사이에 연결
  • 이전 요소 : 새로운 요소 참조
  • 새로운 요소 : 다음 요소 참조
• 삽입할 위치를 찾고(O(N)) 삽입 연산을 진행하므로 O(N)의 시간 복잡도를 가짐

삭제 연산 - O(1)

• 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경
• 배열처럼 데이터를 이동하기 위해 복사할 필요가 없어 처리 속도가 훨씬 빠름
• 삭제하고자 하는 원소를 찾는 과정 때문에 O(N)의 시간 복잡도를 가짐

활용

• 삽입/삭제 연산이 자주 일어나고 검색 빈도가 적은 경우