연결리스트란?

연결리스트는 일반적인 리스트와 다르다. 리스트는 인덱스를 이용해 데이터를 저장하지만 연결리스트는 앞 뒤 데이터를 연결하며 데이터를 저장한다. 예를 들어 일반적인 리스트의 경우 리스트 원소들 중 가운데에 특정값을 추가하고 싶다면 특정값을 추가한 뒤, 추가된 특정값 뒤 모든 값들의 인덱스를 +1 해준다. 이때 추가된 특정값 뒤 모든 값들이 많을 경우 특정값 하나를 추가하는 작업에 너무 많은 시간을 소비하게 된다. 하지만 연결리스트의 경우 연결리스트 원소들 중 가운데에 특정값을 추가하려 할 때 추가할 부분의 앞 뒤 데이터의 연결을 끊어주고 이 사이에 특정값을 넣은 후 다시 앞 뒤 연결만 이어주면 해결된다. 즉, 연결리스트는 리스트에서 데이터를 추가하거나 삭제할 때 소비되는 시간을 단축시키기 위해 만들어졌다.

• 구성성분
  • node : 연결리스트의 하나의 원소
    • head : 제일 앞 node

트리구조란?

부모-자식 관계로 이루어진