연결 리스트

■ 연결 리스트는 왜 쓰느냐?

Z

A

C

R

A

\0

배열을 데이터 삽입과 삭제에 치명적이 약점이 있다!
자 위 ZACRA 라는 Z 앞에 T 라는 문자를 넣으려고 한다고 하면
그냥 생각하면

Z

A

C

R

A

\0

이 배열의 크기를 늘리고

Z

A

C

R

A

\0

T 를 넣고 나머지를 뒤로 쭉 밀면 됩니다.

T

Z

A

C

R

A

\0

이론상으로는 쉽지만 코드 상으로는 상당히 번거로운 일이다.
데이터의 삭제는 어떤가요?
저기서 C를 삭제한다고 치면 C를 삭제하고 그 뒤의 문자들을 또 앞으로 한 칸씩
당겨야 한다. 말은 쉽지만 코드 상으로는 번거롭고
저런 배열의 구조의 단점이 없는 구조가 연결리스트 이다.

■ 연결리스트의 구조

연결 리스트는 그럼 어떤 구조를 가지고 있는가?

Data

next

→

Data

next

→

Data

next

→

Data

next

자 이렇게 연결 리스트는 다음과 같이 데이다 부분과 링크 부분으로 나누어진다.
저 두 부분을 합해서 대략 노드라고 부른다!
위에선 next가 링크 부분!!
실제로 데이터는 뭐 int형이나 char형등으로 나타내면 되고
next부분은 포인터를 써서 나타낸다.
물론 1이란 데이터를 가지고 있는 노드의 next란 포인터는
2란 데이터를 가지고 있는 노드의 주소를 가짐으로써
2번은 3번을, 3번을 4번을.. 이런 식으로
즉, 연결이 되서 연결 리스트가 된다~!!

■ 노드의 생성

대충 그럼 이 연결 리스트의 기본이 되는 노드를 한번 코드 상으로 나타내면
다음과 같이 구조체로 만들 수 있다.

struct node { 
        int data; // 데이터 파트 
        struct node *next; // 링크 파트
};

struct node a, b;
a.data = 1;
b.data = 2;
a.next = &b;

위와 같이 하면 a.next 에 b 노드의 주소가 들어간다.
자 그런 다음 a.next를 이용해 b의 값을 출력해보면
a.next->data;
자 이렇게 하면 b의 값을 출력할 수 있다.

참고 :  이렇게 선언 & 정의하여 많이 쓰인다.
typedef struct list *list_pointer;
struct list
{
     char data;
     list_pointer next;
};


관련 소스
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

struct list{
 int info;
 struct list *next;
};

void main()
{
 int i;
 struct list *head, *temp, *tail;

 printf("숫자들을 입력하세요. 0 입력은 종료입니다\n");
 scanf("%d", &i);

 temp = (struct list *)malloc(sizeof(struct list));
 temp->info=i;
 temp->next=NULL;
 head = tail = temp;

 while(i)
 {
  scanf("%d", &i);
  temp = (struct list *)malloc(sizeof(struct list));
  temp -> next = NULL;
 
  if(i)
  {
   tail->next=temp;
   tail = temp;
   temp->info=i;
  } 
  else free(temp);
 }
 
 while(head != NULL)
 {
  printf("%5d", head->info);
  head=head->next;
 }
}