이중 연결 리스트

이중doubly 링크드 리스트는
한 노드가 자기 앞에 있는 노드를 가리키는 포인터도 가지고 있는 경우를 말한다.

(노드1) <-> (노드2) <-> (노드3) 이렇게

여기서는 맨 앞의 노드를 헤드라고 부른다고.

삽입

1. 맨 앞에 삽입
   1. 새 노드를 만들고
   2. 기존의 헤드의 prev 포인터가 새 노드를 향하게 만든다.
   3. 새 노드의 Next 를 기존의 헤드 노드로
   4. 새 노드의 prev 포인터를 null 로 한다.
2. 맨 끝에 삽입
   1. 새 노드를 만들고
   2. 기존의 마지막 노드의 next가 새 노드를 가리키고
   3. 새 노드의 prev가 기존의 마지막 노드로
   4. 새 노드의 Next를 Null로
3. 중간에 삽입
   1. 새 노드를 만들고
   2. 새 노드의 prev와 next를 각각 지정해주고
   3. 앞 노드의 next와 뒤 노드의 prev를 새 노드로

삭제

삭제도 단일 연결 리스트와 마찬가지로 free()를 통해 메모리를 비워줘야 하는것을 신경써야 한다.

1. 맨 앞 노드 삭제
2. 맨 끝 노드 삭제
3. 중간 노드 삭제

정리

순서가 중요한 데이터들을 모아두는 자료형을 '리스트'라고 하고
가장 간단한건 '배열'이다.
하지만 미리 크기를 지정해야된다는 단점과 안에 요소를 삽입하거나 삭제할때 불편하다는 단점 때문에 '링크드 리스트'라는 자료형을 사용한다.

포인터

링크드 리스트에서 사용되는 '포인터'라는게 등장.
메모리의 주소값을 가리키고있는 변수다.
링크드 리스트는 배열처럼 요소들이 서로 이웃하고 있지 않기 때문에,
리스트에 요소를 넣을 때, 항상 새로운 노드를 만들고 그 노드의 주소값을 이전 노드에 저장한다.
그래서 리스트를 처음부터 끝까지 순회할 때 각 노드에 적힌 주소값들을 타고 타고 이동하는것.

링크드 리스트에 삽입, 삭제

삽입하거나 삭제할 때 신경써야하는 부분이 있다.
새로운 노드를 넣을 때 1) 먼저 새로운 노드를 만들고 새 노드의 포인터에 다음 노드의 주소값을 넣어주고, 2) 그 다음에 새 노드의 주소값을 이전 노드의 포인터에 넣어줘야 한다.
그러지 않고 먼저 새 노드의 주소값을 앞 노드의 포인터에 넣어버리면, 기존에 가지고 있던 주소값이 사라지게 되고 새 노드가 자신의 포인터에 넣을 주소값을 알 수 없게 된다.
삭제할 때에도 마찬가지로 free()함수로 해당 메모리를 비워줘야 하기 때문에 (가비지 컬레거가 없기 때문에) 주소값을 가지고 있어야 한다.
(이런 과정들을 직접 구현해야 하기 때문에 C언어가 공부해볼만 한 언어라고 한다.)