프로그래밍과 잡담

단일 연결리스트와 다른건 struct Node{ int key; struct Node* left; struct Node* right; } 위와 같이 두개로 되어있다. 단일 연결리스트의 단점은 검색을 할때 뒤로 못가는데 이건 그게 가능해진다. 단일의 경우 뒤로 갈려면 환영구조로 해서 한바퀴 돌아서 오는 수 밖에는 없다. 그래서 주로 이중연결리스트를 많이 사용한다. 삽입과 삭제는 단일과 같기 때문에 안쓴다. left에 전 노드의 주소를 넣어주면 된기때문에 그 외에는 다른게 없다. 삭제 할때는 좀 더 편하다. 왜냐하면 찾는 노드가 전에 노드의 주소와 다음 노드의 주소를 가지고 있기때문에 ..바로 이어 줄 수 있다. 이중 ... 단일 노드 -> 노드 -> 노드 -> ...

단순 연결리스트의 기본 구조는 typedef struct _node{ int key; struct _node *next; }Node; 위와 같은 형식을 가진다. 단순연결이기때문에 검색을 할려면 앞에서부터 순차적으로 들어간다. 뒤로 가는건 안됀다 오로지 앞으로만 갈 수 있다. 뒤로갈려면 이중연결리스트를 써야한다. 연결리스트의 단점은 배열보다 용량을 더 잡아먹고, 주소를 잘못 지정하면 전에 있던거나 앞에 있던게 메모리 상에서 떠돌아다니게 된다. 뭔말인고 하니 메모리 누수가 생긴다는거다. 물론 C일 경우에만 Java나 C# 같은 GC(garbage collector)가 있는 랭귀지는 관계 없다. Head -> A - > B - > C - > D -> NULL C를 찾기 위해서는 Head 에서부터 C까지 들어가..