이중연결리스트

이중연결리스트

가장 단순한 이중연결리스트는 다음과 같다. 

정렬된 이중 연결 리스트

모든 노드에 대해 진전 노드로 가는 연결을 충가한 것이 이중 연결이다. 

이렇게 되면 정렬된 연결리스트의 삽입 삭제에 있어서 이전 노드로 되돌아가기가 쉬워진다. 

위의 내용을 코드로 구현하자면 다음과 같다. 

 

 

 

 

만약 연결 리스트에서 삽입 작업이 주로 리스트 끝에서 일어난다면 테일 포인터를 하나 더 두면 된다. 

새로운 노드를 삽입하려면 현재의 테일이 가리키는 노드의 Next가 새 노드를 가리키게 한 후 원래 테일을 이동시켜 새 노드를 가리키게 한다. 

 

연결리스트의 삽입과 삭제가 끝에서 이루어진다면 Tail이라는 포인터를 둔다.

이를 구현한 내용은 다음 링크를 통해 확인 한다. 

2022.04.22 - [C++/자료구조] - 연결 리스트를 이용한 스택 구현

스택에서는 Tail이 Top이 된다.