연결리스트(LinkedList) 개념 정리

소개글

연결리스트(LinkedList) 개념 정리에 대한 보고서 자료입니다.

목차

1.기본개념
2.단순연결리스트
삽입/삭제/스왑/정렬
3.이중연결리스트 및 환상연결리스트
삽입/삭제/스왑/정렬
4.배열을 이용한 연결리스트
삽입/삭제/스왑/정렬

본문내용

의 이전노드가 스왑이 되어야하기 때문에 dpointer2를 가리키게 했다.
dpointer2->llink->rlink=dpointer1 즉 위와 같이 dpointer2의 이전노드도 마찬가지로 스왑이 되어야하기 때문에 dpointer1을 가리키게 했다.
다시 temp에 dpointer1->link값을 넣어준후
dpointer1->link=dpointer2->llink 즉, dpointer1의 llink는 dpointer2의 이전노드를 가리켜야 하기 때문에 위와같이 하였다.
마지막으로 dpointer2->link=temp 즉, dpointer2의 llink값도 또한 dpointer1의 이전노드를 가리켜야하므로 temp에 저장되었던 dpointer->llink값을 넣었다.
스왑이 된부분의 그림이 상당히 복잡하게 되어있다.
하지만 연결선을 따라가보면 그림은 아래와 같이 정리된다.
이번 스왑노드는 조금 복잡한 것 같지만 그렇게 어렵지는 않다.
이중으로 서로 연결해줬을뿐이지 단일연결 리스트와 거의 다를바가 없다.
사람마다 다르겠지만 한노드가 앞뒤로 다 가리키고 있기 때문에 단일보다 쉽다고 생각하는 사람들이 많을 것이다. 나 또한 그렇게 생각한다.
정렬
SortNode() {
node* temp1, temp2;
temp1=temp2=head;
while(temp2->rlink != head)
{
while(temp1->rlink != head)
{
if(temp1->data > temp1->rlink->data)
{
if(temp1 == head)
{
head=temp1->rlink;
temp2=head;
temp3=temp1->rlink->rlink;
temp1->rlink->rlink=temp1;
temp1->rlink=temp3;
temp3->llink=temp1;
head->llink=temp1->llink;
temp1->llink->rlink=head;
temp1->llink=head;
}
오름차순으로 정렬한 부분을 설명 하겠다.
오림차순이 많이 쓰이며 내림차순은 오름차순에서 값 몇 개만 바꾸면 가능하기 때문에 오름차순만 설명하겠다.
먼저 그림과 코딩을 살펴보면 첫 번째 노드와 두 번째 노드의 값을 비교한다.
다음 첫 번째 노드가 값이 크기 때문에 오른쪽노드와 Swap이 되어야한다.
그런데 첫 번째 노드는 head가 가리키는 노드이기 때문에 head는 무조건 처음을 가리켜야 한다는 걸 알고있을 것이다.
그래서 if(temp1==head)라는 if문을 이용하여 head가 Swap될경우에 대비하였다
일단 head가 바뀌기 때문에 head는 오른쪽 노드르 가리켜야 하므로 head=temp1->rlink가 되고,
temp3=temp1->rlink->rlink 즉, temp3가 3번째째 노드를 가리킬수 있도록 하며,
2번재 노드의 즉, head가 가리키고 있는 노드의 rlink가 temp1을 가리키게 하며,
temp1->rlink는 아까 저장했던 temp3의 값 즉, 3번째 노드를 가리키게 한다.
다음 3번째 노드의 llink는 1,2번째 노드가 서로 Swap이 되기 때문에 temp1을 가리켜야 하므로 temp3->llink=temp1
head->llink는 항상 마지막 노드를 가리켜야 하므로 head->llink = temp1->llink가 되고,
temp1->llink->rlink 즉, 마지막 노드는 항상 head를 가리켜야 하므로 temp1->llink->rlink=head가 된다.
마지막으로 temp1은 head와 Swap되기 때문에 head를 가리켜야 하므로 temp1->llink=head가 된다.
이렇게 head==temp1일 때 의 정렬 부분이 끝나고 다음 스왑이 된후 head!=temp1일때의 내용이 나온다.
else
{
temp3=temp1->rlink->rlink;
temp1->rlink->rlink=temp1;
temp1->rlink=temp3;
temp3->llink->llink=temp1->llink;
temp1->llink->rlink=temp3->llink;
temp1->llink=temp3->llink;
temp3->llink=temp1;
}
}
이 else부분의 그림고 코딩내용은 위의 head부분의 내용과 거의 차이가 없다.
역시 temp1부분이 다음 노드보다 값이 크기 때문에 Swap이 될것이다.
다만 head가 swap되는 일은 이제 없기 때문에 더 간단하다.
먼저 temp3에 temp1->rlink->rlink 즉 4번째 노드의 값을 저장하고
temp1->rlink->rlink(3번째 노드)가 2번째 노드 즉, temp1을 가리키게 한다. 왜냐하면 두 값이 바뀔것이기 때문이다.
다음 temp1->rlink는 temp3의 값을 가져야한다.
다음 temp3->llink->llink 즉, temp1노드의 다음노드가 temp1노드의 앞노드를 가리켜야 하므로 temp3->llink->llink=temp1->llink가 되고
temp1->llink->rlink 즉, temp1노드의 이전노드의 rlink가 temp1노드의 다음 노드를 가리켜야 하므로 temp1->llink->rlink=temp3->llink가 된다.
temp1->llink는 스왑될 노드의 다음노드를 가리켜야 하므로 temp1->llink = temp3->llink가 되고,
마지막으로 temp3->llink=temp1 이 된다.
이렇게 해서 현노드가 다음노드보다 클때의 조건이 모두 마무리 되었다.
이제 만약 현노드가 뒤의 노드보다 값이 작을 경우에 대해서 설명하겠다.
else
{
temp1=temp1->rlink;
}
}
temp1=head;
temp2=temp2->rlink;
}
}
위의 그림과 코딩을 살펴보자.
이번부분은 현노드가 다음노드보다 값이 더 작았다.
그러므로 그냥 다음노드를 temp1이 가리키게 하면 된다.
그래서 temp1=temp1->rlink로 끝이나고
다음 else문이 끝나고 while문이 끝난다음 다시 처음노드부터 검사를 해서 노드를 Swap해 주어야 하기 때문에 temp1=head가 선언되었고,
처음노드부터 다시 모두 바뀔 때 까지 돌기위해서 중복 while을

키워드

연결리스트,   LinkedList,   이중연결리스트,   환상연결리스트,   단일연결리스트,   C언어,   포인터,   구조체