링크드리스트

정의 : 일정한 순서를 가지는 데이터 항목을 표현하는 방법, 배열과 같은 순차적표현 방법과는 달리 데이터 항목들의 논리적 순서만 유지되고 기억장소 내에 각 항목들의 임의의 위치를 가지도록 하는 자료구조

구조 :  각 데이터 항목들이 기억장소 내의 어떤 위치에 있는지 표시, 데이터 항목에 값뿐 아니라 다음 항목의 위치정보도 저장, 위치 정보 저장에는 포인터를 사용한다.

장점 : 기억공간의 활용도가 매우 높다. 데이터 삽입,삭제가 수월하다.

단점 : 데이터 직접접근이 거의 불가하다. (순차적접근만이가능), 링크손실에 대한 복구 거의불가, 포인터를통해사용하기떄문에 포인터추가적인 기억공간필요

--------------------------------------------------------------------------------------------------------

단일 연결 리스트

연속된 원소들이 기억장소 내에서 어느 곳에나 저장 가능하도록 원소들의 위치와 무관하게 원소들을 연결하여 표현하는 방법, 리스트의 한 원소의 노드(node)는 원소값을 저장하는 자료(data), 다음 원소를 지적하는 포인터값을 저장하는 링크(link)로 구성

장점 : 연결 리스트의 모든 장점을 가지고 있다. 가정 융통성이 높다.

단점 : 복잡도가 높다. 많은 기억 공간이 필요하다.

환형 연결 리스트

마지막 노드의 링크 값이 NULL이 아니라 리스트의 첫번째 원소의 주소를 가리킴.

노드의 시작과 끝은 구별하지 않음 -> 마지막 노드와 처음의 노드가 연결되어 있음

임의의 노드에서 시작하여 모든 노드로의 접근이 가능 -> 검색시 용이

정보가 끊어지면 극복이 가능

장점 : 임의의 노드로부터 모든 노드로의 접근이 용이, 리스트에 노드 삽입/삭제 시 노드 수에 관계없이 일정한 시간 소요 -> 삽입과 삭제 연산이 용이, 리스트의 결합, 분리 작업이 효율적이다.

단점 : HEAD노드 ->검색시 무한 루프에 빠질 가능성 존재, 검색을 끝낼 수 있는 노드필요

이중 연결 리스트

링크가 두개 존재한다.  즉 검색 시 양방향으로 노드 검색

좌링크 : 선행 노드

자료 필드

우링크 : 후행 노드

로 구성된다.

장점 : 임의의 노드를 검색할 때 양방향으로 접근 가능, 임의의 노드의 연결이 파괴되었을 시 복구 가능

단점 : 전위와 후위 역녈을 위한 포인터 기억 공간이 필요함.

그외에 이중 환형 연결리스트도 있음.

출처 : http://internet512.chonbuk.ac.kr/multilec.htm

다만, 한번 반복숙달해보는것이지만, STL이 나는 편한것같다;;

대략적으로 다시 기억을 되살리면..

#include <stdio.h>

#include <malloc.h>

/***********************************

*링크드리스트 표현

***********************************/

typedef struct _data

{

char* pDay;

}data;

typedef struct _node

{

data data;

_node* pNode;

}node;

int main(void)

{

node *head;

head = (node*)malloc(sizeof(node));

head->data.pDay = (char*)malloc(sizeof(char)*2);

head->data.pDay = "월";

head->pNode = NULL;

node *pNode;

pNode = (node*)malloc(sizeof(node));

pNode->data.pDay = (char*)malloc(sizeof(char)*2);

pNode->data.pDay = "화";

head->pNode = pNode; //헤더주소와 이 노드를 연결함으로써 리스트적용

pNode->pNode = NULL; //가장 마지막 노드는 null이 된다.

//① pNode->pNode = head;  여기에 이걸적용하면 환형리스트가 될것이다.

while(head != NULL)

{

printf("%s\n",head->data.pDay);

head = head->pNode;

}

return 0;

}

#include "stdio.h"
#include "windows.h"

typedef struct _node
{
 char a;
 _node *link;
}node;

int main()
{
 node* pNode = NULL;
 node* pHead = NULL;
 node* pTop = NULL; //pHead의 첫주소를 받는다.

 pHead = (node*)malloc(sizeof(node));
 pHead->a = 0;
 pHead->link = NULL;

 pTop = pHead;

 for(int i=1; i<=100; i++)
 {
  pNode = (node*)malloc(sizeof(node));
  pNode->a = i;
  pNode->link = NULL;
  pHead->link = pNode;

  pHead = pNode;
 }

 pHead = pTop;

 while(pHead->link != NULL)
 {
  printf(" %c \n",pHead->a);
  pHead = pHead->link;
 }

 return 0;
}