[ 자료구조 및 알고리즘 ] 5.연결 자료구조 - 1.연결 자료구조

순차 자료구조 

장점

• 논리적인 순서와 물리적인 순서가 동일 ⇒ 원소의 위치를 찾아 접근하기 쉬움

 

 문제점
• 삽입연산이나 삭제연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간 소요
− 원소들의 이동 작업으로 인한 오버헤드 발생
− 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능상의 문제 발생

 

통상 배열을 이용하여 구현
• 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐

 

⇒ 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법 필요

 

순차자료구조의 장점은 논리적 순서와 물리적 순서가 동일하다보니 논리적인순서,시작위치,데이터원소의 크기만 알면 특정 논리적 원소의 순서값을 가지고 물리적인 위치값을 계산해서 다이렉트로 접근하기가 쉽다. 단점: 중간에 삽인 삭제할때 논리적 순서와 물리적 순서를 동일 하게 유지를 하기 위해서 추가적으로 해당 위치 이후로 추가로 이동시켜주는 작업과 시간이 소요 즉 추가 비용이 발생함.

 

연결 자료구조(Linked Data Structure)

자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조

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

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

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

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

 

연결 리스트

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

− 단순 연결 리스트
− 원형 연결 리스트
− 이중 연결 리스트 

−이중 원형 연결 리스트

이런 단점을 개선하기 위해 논리적 순서와 물리적 순서가 동일할 필요가 없는 연결 자료구조(연결 리스트)를 만듬. 연결자료구조는 논리적인 순서와 물리적인 순서가 동일할 필요는 없는 대신 다음 원소를 찾아갈수있게 위치값을 같이 저장해 주소를 제공해주는 방식이다. 즉 데이터+다음 데이터 위치값을 같이 저장하는 방식. 연결리스트는 위치값이 몇개가 있느냐에 따라서 단순연결리스트 singly linked list (링크1, line), 원형 연결리스트(링크1, 원형), 이중 연결리스트(링크2, line), 이중 원형 연결리스트(링크2, 원형)가 있다.

 

연결 리스트의 노드

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

- <원소값, 주소>의 구조

 

• 데이터 필드(data field) 

− 원소의 값을 저장

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

 

• 링크 필드(link field)

− 다음 노드의 주소를 저장
− 포인터 변수를 사용하여 주소값을 저장

연결리스트에서는 하나의 단위를 노드라고 부르는데 노드는 데이터필드(원소값) + 링크필드(다음 노드의 주소)로 구성됨. 데이터필드는 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성 링크필드는 c언어로 구현하면 포인터 변수 객체지향 언어c++.java로구현할 경우 reference변수로 구현 하게됨.

//c
struct Node{
		char data[4];
		struct Node*link; 
};
//객체지향
 class Node{
		char data[4];
		class link;
};

선형리스트를 연결 리스트로 구현한다고 했을때 리스트 이름을 첫번쨰 노드를 가리키는 변수로 구현한다. 제일 마지막은 null. 링킅드리스크는 무조건 헤드 포인터(시작변수)부터 순서대로 각각의 노드에 접근해야함. 중간에 다이렉트로 접근은 불가능. 공백 연결리스트 즉 원소가 없는 리스트는 시작 변수를 null포인터로. 링크드리스트의 장점은 중간에 삽입삭제는 쉬운데 특정원소의 위치값을 바로 계산할 수 없기 때문에 순서대로 접근을 해 연산을 원하는 노드까지 순서대로 이동을 해야하기 때문에 시간이 오래걸림. 자유공간 리스트: 운영체제에 받아서 쓰고 돌려주는게 아니라 메인 메모리 영역(freespace)을 추가로 받아서 자체적으로 메모리가 필요할 때마다 자기 안에서 돌려서 관리하고 쓰는 방법. 할당(요청):getnode() 해서 쓰다가 반환:returnnode()하면 다시 사용가능한메모리로 재 활용을 함 . 할당과정은 몰라도됨. 운영체제에 받아서 쓸 때는 객체지향: new 로 바로 만들어서 construct해서 쓰고 distwctor로 돌려줌 c언어: malloc 받아쓰고 free로 돌려줌

 

노드 연결 방법에 대한 이해 - 기차놀이

1 이름표 뽑기

2 자기가 뽑은 이름의 사람을 찾아서 연결하기 : 승희→상원 →수영

− X표를뽑은사람은마지막기차
− 기차는 이름표를 들고 있는 방향으로 움직인다.

 

• 기차놀이와 연결 리스트

− 기차놀이 하는 아이들 : 연결리스트의 노드

 − 이름표 : 노드의 링크 필드

 

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

• 리스트 week=(월, 화, 수, 목, 금, 토, 일)

• week에 대한 선형 리스트

 

• 리스트 week=(월, 화, 수, 목, 금, 토, 일) 

• week에 대한 연결 리스트

 

 

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

• 리스트 이름 week

−  연결 리스트의 시작을 가리키는 포인터변수

−  포인터변수 week는 연결 리스트의 첫번째 노드를 가리키는 동시에 연결된 리스트 전체 를 의미

 

• 연결 리스트의 마지막 노드의 링크필드 

− 노드의 끝을 표시하기 위해서 null(널) 저장

 

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

 

• 각 노드의 필드에 저장한 값은 포인터의 점 연산자를 사용하여 액세스
− week.data : 포인터 week가 가리키는 노드의 데이터 필드 값 “월”
− week.link : 포인터 week가 가리키는 노드의 링크 필드에 저장된 주소값 “120”

• 리스트 week의 노드에 대한 C 프로그램 구조체 정의

struct Node{
	char data[4];
	struct Node* link; 
};