Doubly Linked List & Circular Linked List

💡 이중 연결 리스트 & 원형 연결 리스트

전에 만들었던 단순 연결 리스트에 previous 필드를 추가한다
즉, 이중 연결 리스트의 Node 구성은 next & prev & data 3개의 요소가 들어감

원형 연결 리스트(Circular Linked List)

tail.next가 null이 아닌 연결 리스트의 노드를 가리키는 연결리스트

단순 연결 리스트의 단점
tail 포인터가 있더라도 removeLast()를 하기 위한 시간복잡도는 O(n)으로
마지막 요소부터 앞으로 넘어갈 방법이 없으므로 비효율적이다.
무조건 처음부터 시작해서 마지막의 2번째 요소까지 와야 마지막 요소를 삭제 할 수 있었다

왼쪽 - 이중 연결 리스트 & 오른쪽 - 원형 연결 리스트

이중 연결 리스트

• previous 필드를 추가함으로써 처음부터 순회를 하지 않고 임의의 포인터도 만들 필요가 없으며,
  시간 복잡도도 O(1)로 바뀐다
• tail.previous.next = null로 가리키고 tail = tail.previous 로 포인터를 이동해주면
  기존의 마지막 요소를 가리키는 대상이 전부 없으지므로 가비지 컬렉션 대상이 되고
  남은 data 객체를 반환하고 필요에 따라 currentSize도 반영해주면 된다

원형 연결 리스트

• 임시 포인터 2개를 활용해서 리스트가 원형인지 확인할 수 있다
• tail이 head를 가리키는 경우
  • head에서 시작해서 임시포인터가 null이 될떄 까지 반복하면 시간복잡도는 O(n)
  • tail.next를 사용한다면 시간복잡도는 O(1)
  • 임시 포인터를 만들어 임시포인터.next == head
• tail이 리스트의 다른 요소를 가리키는 경우
  • tail에서 시작하여 tail 포인터가 다시 나타나는지 확인, 이때 시간복잡도는 O(n)
  • 임시 포인터 2개를 사용하여 시작점을 잡고 currentSize 만큼 떨어진 노드까지 확인 후,
    시작점을 다음으로 옮겨갈때까지 반복, 이때 시간복잡도는 O(n^2) 이다