Linked list

연결리스트

• 차례로 연결된 노드를 표현해주는 자료구조

• 단방향 연결리스트 : 각 노드는 다음 노드를 가리킨다.

• 양방향 연결리스트 : 각 노드는 다음 노드와 이전 노드를 함께 가리킨다.

• 장점

  • 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간안에 할 수 있다는 점

• 단점

  • 배열과는 다르게, 연결리스트의 경우, 특정 인덱스를 상수 시간에 접근할 수 없다.

    • K번째 원소를 찾고 싶으면 K번 루프를 돌아야하는 셈!

노드

• <원소, 다음 원소의 주소> 단위로 저장을 해야한다. 이런 단위 구조를 노드라고 한다.

• <data 필드, link 필드>

연결리스트 만들기

• head 노드의 주소를 참조하는 방법

• LinkedList 자료구조를 사용하는 방법

단방향 연결리스트에서 노드를 삭제하는 경우

Runner 기법

• 연결 리스트를 순회할 때, 두개의 포인터 동시에 사용하는 것

• 한 포인터가 다른 포인터를 반드시 앞서도록 한다.

• 앞선 포인터는 따라오는 포인터보다 항상 지정된 개수만큼 앞서도록 할 수 있고, 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있다.

재귀 문제

• 재귀 호출 깊이가 n이 될 경우, O(n)만큼의 공간을 사용한다.

• 모든 재귀는 반복문으로 구현 가능하고 그 반대도 가능하다. 코드는 재귀가 간단하고 시간은 반복문이 더 빠른 것이 보통이다.