This Week's Mission Agenda

1. 여러 복잡도 학습 및 정리
2. 연속배열과 링크드리스트의 차이점 비교, 언제 어떤 게 더 효율적인지 알기
3. 싱글, 더블, 서큘라 리스트 각각의 특성과 효율성 비교
4. 작성한 코드의 복잡도와 속도 정리

What I Learned

• Array: Fixed/Static Array -> 정적, 메모리 안에 피지컬리 붙어있다. 배열안의 값을 검색하고 가져오는데에 용이하지만 처음 생성할 때 사이즈가 정해져있어서 데이터를 추가하고 삭제하는데에는 비효율적이다.
• List: Dynamic Array -> 동적, 데이터가 다음 데이터를 가리키고 있는 형태로 사이즈가 고정되어있지 않아 데이터를 추가하고 삭제하는데에 용이하지만 탐색하려면 하나씩 돌아야해서 비효율적이다. 그리고 한 노드당 값과 다음 연결 리스트를 저장해주어야해서 메모리상으로도 연속배열보다 비효율적이다.

Linked List

Linked List is a linear collection of data elements whose order is not given by physical placement in memory but each element points to the next.

• 길이가 정해져 있지 않고 중간에 데이터를 자유롭게 넣고 뺄 수 있다는 장점이 있다.
• 주소를 타고 타고 데이터를 가져와야 해서 연속배열에 비해 비교적 느리다.
• 한 노드 안에는 두 개의 필드(변수)가 있다.
  • Data Field: 실제 데이터, 노드의 값
  • Link Field: 노드가 가리키는 다음 노드의 주소값

링크드 리스트의 종류

• 싱글(단방향): 한 방향으로만 이동 가능. 한 노드당 한 개의 링크가 있다. 탐색하려면 헤드부터 순차적으로 탐색해야한다.
• 더블(양방향): 양 방향으로 이동 가능. 한 노드당 두개의 링크가 있다. 탐색한 노드의 전과 후 노드를 찾는데에 용이하다.
• 서큘라: 마지막 노드가 첫번째 노드를 가리켜서 회전할 수 있게 한다. 탐색할 때 헤드부터 돌아가서 탐색할 필요가 없다.

To Add a Node