Linked List

• Reference
• Tree, Graph의 근간이 되는 자료구조
• remove, merge, 교차점 찾기, 루프 찾기 등이 핵심

struct
{
	val
    addr
}

• 위와 같이 Val, 다른 노드 Addr을 갖고있는 녀석이 노드다.

o -> o -> o

• val, addr을 갖고있는 노드를 o 라고하면, 서로 연결한 모습이 위와 같다.
• -> 는 addr에 위에 정의한 노드의 메모리상 주소값을 저장함으로써 Linked 되었음을 의미한다.
• Find 연산 시 head에서 시작해서 노드를 타고 들어가므로 O(n)의 Time Complexity가 걸린다.
• array의 random access는 O(1)이다. Linked List는 각각의 노드를 들러야하므로 TC(Time Compleixty)가 O(n)이다.
  • Linked List 는 random access라 하지 않고 traverse 라고 한다.
• Delete, Insert는 TC가 O(1) 이다.

o <-> o <-> o ...

• 맨 처음은 Singly linked list 라고 하고, 위와 같은 경우는 Doubly linked list라 부른다. 역시 addr 변수를 하나 더 둬서 prev와 next노드의 메모리 address를 저장하는 것이다.
  • Doubly Linkd list는 Head에서 뿐만 아니라 Tail에서도 탐색이 가능해지는 것이 특징이다.
• 노드를 가지고 노는 방법을 암기 수준으로 알고 있어야 잘 풀 수 있다.