'링크드리스트'에 해당되는 글 2건

  1. 2009.04.04 [LinkedList] Insertion Sort (삽입정렬)
  2. 2009.03.29 [LinkedList] reverse
중대 컴공2009.04.04 03:31

배열을 이용한 삽입정렬은 쉽게 구현할 수가 있다. Index를 이용해서 값들을 옮기기 쉽기 때문이다.

그런데... 단일 링크드 리스트에서 삽입정렬은... 처음에는 상당히 난감했다... key값을 3개를 가지고 비교값도 3개를 가지고 했었다.... key앞,key,key뒤 이렇게 3개를 가지는것이다.... 하지만... 실패 ^^; 실패의 원인은 key에 대해 잘못 이해하고 있었음;

두번째 시도에서는 그림을 그려서 해보았음. 오랜 시간의 삽질이 있었지만.. 결국 성공했다... 하지만.. 이게 최적일까 -_-;

아무튼 생각하기 위해 그린 그림을 완성후 다시 정리하여 그려 보았습니다.

신고
Posted by 초프(초보 프로그래머)
중대 컴공2009.03.29 00:15

LinkedList에 저장되어있는 값들을 역순으로 정렬하는 것이다.

처음에 생각한 것으로는 처음부터 끝까지 한번 돌면서 Stack에 하나씩 주소를 push 해주는 것이다.

그리고 하나씩 pop하면서 다시 LinkedList를 연결한다. 그러면 마지막 주소부터 하나씩 새로 Link해주는 것이다.


위와 같은 순서로 진행된다.

하지만....

교수님의 얘기는 처음부터 끝까지 한번 움직이면 역순으로 정렬이 되어야 한다고 한다.....;

포인터 3개로 하면 가능하다고 한다.

다음이 내가 고민끝에 생각해낸 결과이다.


분명 빨간색 펜이었는데.... 검정색으로 스캔이 되어버렸다는;;;
신고
Posted by 초프(초보 프로그래머)