연결리스트배열을 사용하여 데이터를 순차적으로 저장하고 나열할 수 있다.
배열을 사용하는 경우 메모리 공간이 불 필요하게 낭비될 수 있다.
배열기반의 리스트배열로 만들었으므로 특정한 위치의 우너소에 즉십 접근할 수 있다는 장점
데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점이 있다.
원하는 위치로의 삽입이나 삭제가 비효율적이다.
#include<stdio.h>
#include<stdlib.h>
#define INF 10000
int arr[INF];
int count=0;
void addBack(int data){
arr[count]=data;
count++;
}
void addFirst(int data){
for(int i=count;i>=1;i--){
arr[i]=arr[i-1];
}
arr[0]=data;
count++;
}
void removeAt(int index){
for(int i=index;i<count-1;i++){
arr[i]=arr[i+1];
}
count--;
}
void show(){
for(int i=0;i<count;i++){
printf("%d\n"),arr[i]);
}
}
int main(void){
addBack(6);
addBack(5);
addFirst(1);
addFirst(4);
show();
system("pause");
return 0;
}
포인터 연결리스트구조체와 포인터를 함께 사용하여 구현한다.
연결리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있다.
필요할 때마다 메모리 공간을 할당 받는다.
삽입과 삭제가 많을 경우 포인터 연결 리스트가 더 효율적이다
하지만 인덱스를 통해 즉시 접근해야 할때는 배열 기반 리스트가 효율적이다.
단일 연결 리스트
#include<stdio.h>
#include<stdlib.h>
typedef struct{
int data;
struct Node *next;
}Node;
Node *head;
void addFront(Node *root,int data){
Node *node=(Node*)malloc(sizeof(Node));
node->data=data;
node->next=root->next;
root->next=node;
}
void removeFront(Node *root){
Node *front=root->next;
root->next=front->next;
free(front);
}
void freeAll(Node *root){
Node *cur=head->next;
while(cur!=NULL){
Node *next=cur->next;
free(cur);
cur=next;
}
}
void showAll(Node *root){
Node *cur=head->next;
while(cur!=NULL){
printf("%d ",cur->data);
cur=cur->next;
}
}
int main(void){
head =(Node*)malloc(sizeof(Node));
head->next=NULL;
addFront(head,2)
addFront(head,3);
addFront(head,4);
removeFront(head);
showAll(head);
freeAll(head);
system("pause");
return 0;
}
연결리스트 구현에서 주의할 점
삽입 및 삭제 기능에서의 예외 상황(메모리 공간이 부족하다 or 삭제할 데이터가 없다) 처리할 필요가 있다.
양방향 연결 리스트머리(head)와 꼬리(tail)를 모두 가진다는 특징이 있다
양방향 연결 리스트의 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장할 수 있다.
리스트 앞에서부터 혹은 뒤에서부터 모두 접근 가능하다.
오른차순 정렬 양방향 연결 리스트
#include<stdio.h>
#include<stdlib.h>
typedef struct{
int data;
struct Node *prev;
struct Node *next;
}Node;
Node *head, *tail;
void insert(int data){
Node *node=(Node*)malloc(sizeof(Node));
node->data=data;
Node *cur;
cur=head->next;
while(cur->data<data&&cur!=tail){
cur=cur->next;
}
Node *prev=cur->prev;
prev->next=node;
node->prev=prev;
cur->prev=node;
node->next=cur;
}
void removeFront(){
Node *node=head->next;
head->next=node->next;
Node *next=node->next;
next->prev=head;
free(node);
}
void show(){
Node* cur=head->next;
while(cur!=tail){
printf("%d ",cur->data);
cur=cur->next;
}
}
int main(void){
head=(Node*)malloc(sizeof(Node));
tail=(Node*)malloc(sizeof(Node));
head->next=tail
head->prev=head;
tail->next=tail;
tail->prev=head;
insert(2);
insert(3);
insert(4);
removeFront();
show();
system("pause");
return 0;
}