20.01.06) DataStructure - LinkedList(ongoing)

목차

• 연결리스트란?
• 연결리스트 구현 코드

  핵심

• 연결리스트는 배열의 삽입과 삭제를 보완한 자료구조이다.

연결리스트란?

연결리스트는 각 원소가 포인터로 연결되어 있는 자료구조를 말한다. 왜 태어났을까? 배열이 가진 단점을 보완하기 위해 등장했다. 배열은 원소의 삽입과 삭제 시 그 뒤에 있는 원소들이 줄줄이 움직여야 한다.

그렇기에 삽입과 삭제시 선형 시간 복잡도를 가진다. 연결리스트는 이런 배열의 단점을 포인터로 극복한다. 각 원소는 메모리에서 따닥따닥 붙어 있지 않다. 각 원소는 이전 혹은 이후 원소의 주소를 참조한다.

주소를 참조하기 때문에 메모리에 따닥따닥 붙어있지 않는다. 그러면 삽입과 삭제의 시간이 단축될까? 그렇다. 삽입과 삭제시 주변 원소의 포인터를 조정해주면 된다. 그러면 상수 시간 복잡도를 가진다.

연결리스트 구현 코드