/****************************************************************************
// 연결리스트 !!
// -> 배열의 단점을 극복하기 위한 동적 자료구조 !
// -> 정적 --> 동적배열 -> 연결리스트 !!
// -> 중간에서 삽입 삭제 문제 !!
//****************************************************************************
// 1) 필요할때만 동적으로 생성하여 사용한다 !!
// 2) 링크에 변경을 통해서 삽입 삭제가 빠르다 !!
//****************************************************************************
//****************************************************************************
// 단일연결리스트 ( head, tail ) 더미 노드활용 !!
//****************************************************************************
#include <stdio.h>
#include <stdlib.h>
//****************************************************************************
// 구조체 선언
//****************************************************************************
typedef struct _Node
{
int date; // 데이타 저장 변수
struct _Node * next; // 링크!!
}Node;
//****************************************************************************
//더미 포인터 선언
//****************************************************************************
Node *head, *tail;
//****************************************************************************
// 초기화 !!
// 기능 : head , tail 생성 및 링크 연결 !!
//****************************************************************************
void init()
{
head = (Node *)malloc(sizeof(Node));
tail = (Node *)malloc(sizeof(Node));
head->next = tail;
tail->next = tail;
head->date = 0;
tail->date = 0;
}
//****************************************************************************
void push_back(int date) // 리스트의 맨 뒤에 삽입
{
// 1) 노드 생성 초기화 !!
Node *newnode = (Node *)malloc(sizeof(Node));
newnode->date = date;
newnode->next = NULL;
// 2) tail 앞에 노드 !!
Node *p = head;
while(p->next != tail){
p = p->next;
}
newnode->next = p->next;
p->next = newnode;
}
//****************************************************************************
void push_front(int date) // 리스트의 맨 앞에 삽입
{
Node *newnode = (Node *)malloc(sizeof(Node));
newnode->date = date;
newnode->next = NULL;
newnode->next = head->next;
head->next = newnode;
}
//****************************************************************************
void insert(int key, int date) //key값 뒤에 삽입
{
Node * p = head->next;
while(p->next != tail){
if(p->date == key){
Node * newnode = (Node *)malloc(sizeof(Node));
newnode->date = date;
newnode->next = p->next;
p->next = newnode;
return;
}
else{
p = p->next;
}
}
push_back(date);
}
//****************************************************************************
void front_insert(int key, int date) //key값 앞에 삽입
{
Node * p = head->next;
while(p->next != tail){
if(p->next->date == key) {
Node * newnode = (Node *)malloc(sizeof(Node));
newnode->date = date;
newnode->next = p->next;
p->next = newnode;
return;
}
else{
p = p->next;
}
}
push_back(date);
}
//****************************************************************************
// 삭제 함수
//****************************************************************************
//맨 뒤의 노드를 삭제 !!
//****************************************************************************
void pop_back()
{
Node *p, *s;
p = head->next;
s = head;
while(p->next != tail){
s = p;
p = p->next;
}
s->next = p->next;
free(p);
}
//****************************************************************************
//맨 앞의 노드를 삭제 !!
//****************************************************************************
void pop_front()
{
if(head->next == tail){
printf("list empty !! \n");
}
else{
Node *p;
p = head->next;
head->next = p->next;
free(p);
}
}
//****************************************************************************
// date에 해당하는 노드 삭제!!
//****************************************************************************
void erase_value(int date)
{
Node *p,*s;
p = head->next;
s = head;
while(p->next != tail){
if(p->date == date){
s->next = p->next;
free(p);
return;
}
else{
s=p;
p = p->next;
}
}
printf("No date");
puts("");
}
//****************************************************************************
// 1번째 3번째
//****************************************************************************
void erase_idx(int idx)
{
Node *p,*s;
p = head->next;
s = head;
int i=0;
while(p->next != tail){
if(i == idx-1){
s->next = p->next;
free(p);
return;
}
else{
s = p;
p = p->next;
}
i++;
}
printf("No date");
puts("");
}
//****************************************************************************
// 출렵 함수( 리트스의 모든 원소를 출력)
//****************************************************************************
void show()
{
Node * p = head->next;
while(p != tail){
printf("%d --> ",p->date);
p = p->next;
}
puts("");
}
//****************************************************************************
void main()
{
init();
push_back(10);
push_back(20);
push_back(30);
push_front(100);
push_back(200);
erase_idx(1);
show();
}
'Programing > 자료구조' 카테고리의 다른 글
| 단일연결리스트.cpp (0) | 2016.11.30 |
|---|---|
| 단일연결리스트.h (0) | 2016.11.30 |
| 이중연결리스트 (0) | 2016.11.30 |
| 단일연결리스트 head만 사용 (0) | 2016.11.30 |
| 자료구조 (0) | 2016.11.30 |