[자료구조]링크드 리스트(Linked List)

선형리스트

- 배열에서 원소 삽입 방법을 살펴 보자.

질문)  위와 같은 경우 배열의 데이터가 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;
}

 

 

 

인천 서구 검단신도시 원당컴퓨터학원