[자료구조]이중 연결리스트

단일 연결리스트와 다른건

struct Node{
int key;
struct Node* left;
struct Node* right;
}

위와 같이 두개로 되어있다.

단일 연결리스트의 단점은 검색을 할때 뒤로 못가는데 이건 그게 가능해진다. 단일의 경우 뒤로 갈려면 환영구조로 해서

한바퀴 돌아서 오는 수 밖에는 없다.

그래서 주로 이중연결리스트를 많이 사용한다.

삽입과 삭제는 단일과 같기 때문에 안쓴다.

left에 전 노드의 주소를 넣어주면 된기때문에 그 외에는 다른게 없다.

삭제 할때는 좀 더 편하다. 왜냐하면 찾는 노드가 전에 노드의 주소와 다음 노드의 주소를 가지고 있기때문에 ..바로 이어 줄 수

있다.

이중
<- 전노드  <-   노드 - > 다음 노드 -> ...

단일

노드 -> 노드 -> 노드 -> ...