자료구조(5) - 연결 자료구조와 연결리스트

연결 자료구조Linked Data Structure

ƒ 자료의 논리적인 순서와 물리적인 순서가 불일치

• 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식

−물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음

• 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현

−크기 변경이 유연하고 더 효율적으로 메모리를 사용

ƒ 연결 리스트

• 리스트의 연결 자료구조로 표현

• 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트

 

순차 자료구조와 연결 자료구조의 예

ƒ 순차 자료구조

• 한 덩어리로 된 소시지나 기차처럼 하나로 된 고정 크기 메모리 공간 사용

ƒ 연결 자료구조

• 줄줄이 소시지나 기차처럼 작은 공간을 여러 개 연결하여 전체를 표현

 

연결 리스트의 노드

ƒ 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조

ƒ <원소, 주소>의 구조

• 데이터 필드data field

− 원소의 값을 저장

− 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성

• 링크 필드link field

− 다음 노드의 주소를 저장

− 포인터 변수를 사용하여 주소 값을 저장

 

선형 리스트와 연결 리스트의 비교

• 리스트 이름 week : 연결 리스트의 시작을 가리키는 포인터 변수

− week는 연결 리스트의 첫 번째 노드를 가리킴과 동시에 연결된 리스트 전체 의미

• 연결 리스트의 마지막 노드의 링크 필드 : 노드 끝을 표시하기 위해 NULL(널) 저장

• 공백 연결 리스트 : 포인터 변수 week에 NULL 저장(널 포인터)

• 각 노드의 필드에 저장한 값은 점 연산자를 사용해 액세스

− week.data : 포인터 week가 가리키는 노드 데이터 필드 값 “월”

− week.link : 포인터 week가 가리키는 노드 링크 필드에 저장된 주소값 “160”

재귀호출꼴을 띄고있는&nbsp;

단순 연결 리스트singly linked list의 개념

ƒ 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가짐

ƒ 연결 리스트, 선형 연결 리스트linear linked list , 단순 연결 선형 리스트singly linked linear list

 

단순 연결 리스트에서의 삽입 연산

단순 연결 리스트에서의 삭제 연산

 

앞 노드를 찾음 : 삭제할 원소의 앞 노드(선행자)를 찾음

➋ 앞 노드에 삭제할 노드의 링크 필드값 저장 : 삭제할 원소 “수”의 링크 필드 값을 앞 노드의 링크 필드에 저장

➌ 삭제한 노드의 앞뒤 노드 연결 : 삭제한 노드의 앞 노드인 ‘월’ 노드를 삭제한 노드의 다음 노드인 ‘금‘ 노드에 연결

insertFirstNode(L,x)
new<- getNode();
new.data<-x;
new.link<-L;
L<-new;
end insertFirstNode()

1. 그냥 삽입

2. 첫번째 노드 삽입

3. 중간 노드 삽입 ( 첫번째 노드 주소를 저장하고 있는 포인터 L 이 NULL 이거나 아닐때)

4. 마지막 노드 삽입 ( 연결링크가 NULL임 마지막이라, 아닐경우도 있음 아닐때는 temp가 가리키는 링크필드의 주소가 NULL이 될때까지 이동 - while문)

 

 

삭제

1. 리스트 L 에서 포인터 pre가 가리키는 노드의 다음 노드 삭제 알고리즘 : 포인터 old(삭제할 노드)

deleteNode(L,pre)
if (L=NULL)then error;
else{
	old <- pre.link;
    if(old = NULL) then return;
    pre.link<-old.link;
    returnNode(old);
   }
end deleteNode()

 

노드 탐색 알고리즘

searchNode(L,x)
themp<-L;
while(temp != NULL)do{
	if (temp.data = x)then return temp;
    else temp<-temp.link;
}
return temp;
end searchNode();

 

원형 연결 리스트

- 단순 연결 리스트에서 마지막 노드가 리스트의 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트

-단순 연결 리스트의 마지막 노드의 링크필드에 첫번째 노드의 주소를 저장하여 구성

- 링크를 따라 순회하면 이전 노드에 접근 가능

insertFirstNode(CL,x)
new<-getNode();
new.data<-x;
if(CL=NULL) then{
	CL<-new;
    new.link<-new;
}

else{
		temp<-CL;
        while(temp.link !=CL)do
        	temp<-temp.link;
        new.link<-temp.link;
        temp.link<-new;
        CL<-new;
    }
end insertFirstNode()

 

-리스트 중간에 노드를 삽입하는 알고리즘

insertMiddleNode(CL,pre,x)
new<-getNode();
new.data<-x;
if(CL = NULL)then{
CL<-new;
new.link<-new;
}
else{
	new.link<-pre.link;
    pre.link<-new;
}

end insertMiddleNode()

- 노드 삭제 알고리즘

삭제할 노드의 전 노드의 연결링크를 저장 후

삭제할 노드의 전노드의 연결링크에

삭제할 노드의 다음 노드의 주소 연결

 

 

이중 연결 리스트

이중 연결 리스트의 개념

ƒ 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

ƒ 이중 연결 리스트의 노드 구조와 구조체 정의

• llink(left link) 필드 : 왼쪽노드와 연결하는 포인터

• rlink(right link) 필드 : 오른쪽 노드와 연결하는 포인터

 

이중 연결 리스트에서 노드를 삽입하는 방법

이중 연결 리스트에서 노드를 삭제하는 방법

 

deleteNode(DL, old)
if (DL = NULL) then error;
if (old.llink = NULL) then
DL old.rlink
else {
old.llink.rlink old.rlink
old.rlink.llink old.llink
}
returnNode(old)
End deleteNode()

단순 연결 리스트를 이용한 다항식 표현

™ 다항식 연결 자료구조의 항 삽입 알고리즘

ƒ 다항식 리스트 포인터 PL과 coef 필드 값을 저장한 변수 coef, expo 필드 값을 저장한 변수 expo, 리스트 PL의 마지막 노드의 위치를 지시하는 포인터 last를 매개변수로 사용

 

음... 대충봄