LinkedList(연결리스트)

연결리스트란?

어떠한 데이터를 추가하고 삭제하는 로직이 계속적으로 반복되어질 때 배열을 이용하게 된다면 추가하거나 삭제할 때마다 O(n)의 시간복잡도를 가지게 되는데 이러한 비효율성을 줄이기 위해서 연결리스트(LinkedList)를 사용한다. 연결리스트는 각각의 요소를 포인터로 연결한 선형 자료구조로 각 요소는 노드라 불리며 노드에는 데이터영역과 포인터영역으로 구성된다.

특징

데이터를 추가하거나 삭제하는데에 O(1)의 시간복잡도를 가지게 된다.
단, 이 때 단순히 추가와 삭제에만 O(1)이 걸리는 것이고, 탐색을 할 때에는 O(n)의 시간복잡도를 가지기 때문에 탐색과 추가,삭제를 겹치게 구현하면 안된다.

종류

• 단일 연결리스트(singly LinkedList) : 하나의 노드가 다음의 연결될 노드를 가리킨다.
• 이중 연결리스트(Doubly LinkedList) : 하나의 노드에 다음의 연결된 노드와 이전에 연결된 노드를 가리킨다.
• 원형 연결리스트(Circular LinkedList) : Tail이라 불리는 마지막 노드가 다시 Head라 불리는 처음 노드를 가리킨다.