선형리스트 |
- 배열에서 원소 삽입 방법을 살펴 보자.
질문) 위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삽입 하기 위해서 몇번 연산을 해야 할까?
- 배열에서 원소 삭제 방법을 살펴 보자.
질문) 위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삭제 하기 위해서 몇번 연산을 해야 할까?
순차 자료구조의 문제점 |
- 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요
- 원소들의 이동 작업으로 인한 오버헤드로 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능상의 문제 발생
- 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐
- 순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법 필요
연결리스트(Linked List) |
- 자료의 논라적인 순서와 물리적인 순서가 불일치
- 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결된느 방식
(물리적은 순서를 맞추기 위해 오버헤드가 발생하지 않음)
- 여러개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현
(크기 변경이 유연하고 더 효율적으로 메모리를 사용)
연결리스트의 노드 |
- 연결 자료구조에서 하나의 원소를 표현하기 위한 단위구조
- <데이터, 주소> 의 구조
: 데이터 필드 - 원소의 값을 저장, 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성됨
: 링크필드(주소) - 다음 노드의 주소를 저장, 포인터 변수를 사용하여 주소값을 저장
순차 자료구조와 연결 자료구조의 비교 |
노드에 대한 구조체 정의 |
typedef struct _Node{
int data;
struct _Node *link;
}Node;
연결리스트 정의 |
Node *Head; //맨먼저 접근하기 위한 포인터
Node *CurPos; //이동하기 위한 포인터
연결리스트 마지막에 추가 |
void LinkedLastAdd(Node *data)
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
Head = data;
}
else{
CurPos = Head;
while(CurPos->link!=NULL) //마지막 위치까지 찾아가자
{
CurPos=CurPos->link;
}
CurPos->link=data;
}
}
현재 연결리스트의 값을 출력 |
void LinkOutput()
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
return;
}
else{
CurPos = Head;
while(CurPos!=NULL) //마지막 위치까지 찾아가자
{
cout << CurPos->data << endl;
CurPos=CurPos->link;
}
}
}
선택된 연결리스트 뒤에 삽입 |
void LinkedSelectInsert(Node *Select,Node *data)
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
Head = data;
}
else{
CurPos = Head;
while(CurPos!=Select) //마지막 위치까지 찾아가자
{
CurPos=CurPos->link;
}
data->link = CurPos->link; ///추가하는 데이터에 선택된 위치의 다음 정보를 연결한다.
CurPos->link=data; ///현재 선택된 위치의 다음 위치 에 추가할 데이터를 연결한다.
}
}
선택된 요소 삭제 |
void LinkedSelectDelete(Node *Select)
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
return;
}
else{
if(Select == Head)
{
Head = Head.link; //Head를 삭제하는 경우 Head를 다음 위치에 이동시키자.
elete Select; ///선택된 객체는 삭제하자.
return;
}
CurPos = Head;
while(CurPos->link!=Select) //마지막 위치까지 찾아가자
{
CurPos=CurPos->link;
}
CurPos->link = Select->link; ///선택 된 데이터의 전 링크를 선택된 링크 위치로 이동시키자.
delete Select; ///선택된 객체는 삭제하자.
}
}
사용예제 |
#include <iostream>
using namespace std;
typedef struct _Node{
int data;
struct _Node *link;
} Node;
Node *Head;
Node *CurPos;
void LinkedLastAdd(Node *data)
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
Head = data;
}
else{
CurPos = Head;
while(CurPos->link!=NULL) //마지막 위치까지 찾아가자
{
CurPos=CurPos->link;
}
CurPos->link=data;
}
}
void LinkedSelectInsert(Node *Select,Node *data)
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
Head = data;
}
else{
CurPos = Head;
while(CurPos!=Select) //마지막 위치까지 찾아가자
{
CurPos=CurPos->link;
}
data->link = CurPos->link; ///추가하는 데이터에 선택된 위치의 다음 정보를 연결한다.
CurPos->link=data; ///현재 선택된 위치의 다음 위치 에 추가할 데이터를 연결한다.
}
}
void LinkedSelectDelete(Node *Select)
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
return;
}
else{
if(Select == Head)
{
Head = Head.link; //Head를 삭제하는 경우 Head를 다음 위치에 이동시키자.
elete Select; ///선택된 객체는 삭제하자.
return;
}
CurPos = Head;
while(CurPos->link!=Select) //마지막 위치까지 찾아가자
{
CurPos=CurPos->link;
}
CurPos->link = Select->link; ///선택 된 데이터의 전 링크를 선택된 링크 위치로 이동시키자.
delete Select; ///선택된 객체는 삭제하자.
}
}
void LinkOutput()
{
if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
{
return;
}
else{
CurPos = Head;
while(CurPos!=NULL) //마지막 위치까지 찾아가자
{
cout << CurPos->data << endl;
CurPos=CurPos->link;
}
}
cout <<"\n\n";
}
int main()
{
Node *tmp[10];
for(int i=0;i<10;i++)
{
tmp[i] = new Node;
tmp[i]->data = i+1;
tmp[i]->link = NULL;
LinkedLastAdd(tmp[i]);
}
LinkOutput();
Node *add;
add = new Node;
add->data = 100;
add->link = NULL;
LinkedSelectAdd(tmp[6],add);
LinkOutput();
LinkedSelectDelete(add);
LinkOutput();
return 0;
}
인천 서구 검단신도시 원당컴퓨터학원
'강의자료 > 알고리즘' 카테고리의 다른 글
[알고리즘] convex hull trick (0) | 2020.12.25 |
---|---|
[자료구조] 우선순위큐(Priority Queue) (0) | 2020.11.17 |
[알고리즘]알고리즘 수행시간을 비교해 볼까? (0) | 2020.11.17 |
[알고리즘]그리디(greedy) 알고리즘 (299) | 2019.11.25 |
(기하알고리즘) 반직선의 교점찾기 2 (11) | 2019.07.12 |