소개

안녕하세요 👋 밖에 할 말이 없습니다.
배너에 있는 이 사람이 누구인지 궁금하다면 알고리즘 개념의 발명가인 Khwarizmi입니다.
앞으로 더 발전된 시리즈를 시작할 예정이니 꼭 팔로우 해주세요.

연결된 목록

단일 연결 목록

struct node
{
    char data;
    struct node *next;
}

자기 참조 구조에 대해 전에 이야기했습니다.



첫 번째 요소는 머리라고합니다.

배열은 동적 액세스이며 연결된 목록은 순차적으로 액세스할 수 있습니다. 이는 필요한 요소에 도달하기 위해 이전의 모든 요소를 ​​방문해야 함을 의미합니다. 즉, 배열은 O(n)이고 배열은 O(1)입니다.

둘 다 검색하면 O(n) 이 걸립니다.

struct node *p;
p = head->next->next; // 30
p->next->next->next=p; // 50 will link to 30 , so 60 is lost
head->next=p->next; // 10 will link to 40
printf("%c" , head->next->next->next->next->data); // d

이 연결 목록은 다음 모두에 대해 동일합니다. 연결된 목록에 1개 이상의 노드가 있다고 가정합니다. 1개 노드인 경우 연결된 목록이 특정 작업을 수행할 수 있는지 확인하기 위한 조건을 설정해야 합니다.

단일 연결 리스트 순회

struct node *t;
t = head;
while(t != NULL) { // or while(t) have same meaning
    printf("%d\n" , t->data);
    t=t->next;
}

우리는 t를 사용하고 있습니다. 헤드가 손실되면 전체 노드가 손실되었음을 의미하기 때문입니다.

단일 연결 목록에 요소 삽입

struct node* new = (struct node*)malloc(sizeof(struct node))

이것은 new라는 포인터를 생성합니다.

a) 시작 부분에 삽입:

new->next=head;
head = new;

b) 끝에 삽입

while(t->next != NULL) {
    t=t->next;
}
t->next = new;
new->next = NULL;

c) 특정 요소에 노드 삽입

struct node
{
    int i;
    struct node *next;
}
// asume we need to insert after node 2
while(t->i != 2) 
{
    t = t->next;
}
new->next = t->next;
t->next = new;

단일 연결 리스트에서 노드 삭제

malloc는 우리를 위한 공간을 만들고 free는 malloc에서 가져온 메모리를 해제합니다.

// assume we are resetting the linked list to it's init state
// deleting a node from the head
head = head->next;
free(t);
// deleting a node from the tail
while(t->next->next != NULL) {
    t = t->next;
}
free(t->next);
t->next=NULL;
// delete a specific node
while(t->next->i != 3){
    t = t->next;
}
struct node *t1 = t->next;
t->next = t1->next; // or t->next->next
free(t1);

예 1

struct node
{
    int val;
    struct node *next;
};

void rearrange(struct node *list)
{
    struct node *p , *q;
    int temp;
    if(!list || !list->next) return; // if linkedlist have no or 1 element return
    p = list; q=list->next; // q pointing to 1st element and q to second
    while(q) // while q is not null do
    {
        temp = p->val;p->val=q->val;
        q->val=temp;p=q->next; // swap q and p
        q=p?p->next:0; // if p is pointing to something it will take it otherwise 0
    }
}
// output : 2 1 4 3 6 5 7

재귀를 사용하여 요소 인쇄

// print then recursion
void f(struct node *p)
{
    if(p)//1
    {//2
        printf("%d" , p->data);//3
        f(p->link);//4
    }//5
}
// output : 1 2 3 4

다음 스택으로 이동하기 전에 인쇄됩니다.



되돌아 가면 5 행으로 돌아갑니다.

// recursion then print === print in reverse order
void f(struct node *p)
{
    if(p)//1
    {//2
        f(p->link);//3
        printf("$d" , p->data);//4
    }//5
}

// output : 4 3 2 1

그런 다음 되돌아갈 때 각 스택 내부에 저장된 p의 값을 인쇄하는 4행에서 시작합니다.

반복을 사용하여 단일 연결 목록 뒤집기

struct node
{
    int i;
    struct node * next;
}
struct node * reverse(struct node * cur)
{
    struct node *prev = NULL,*nextNode = NULL;
    while(cur)
    {
        nextNode = cur->next;
        cur->next=prev;
        prev=cur;
        cur=nextNode;
    }
    return prev;
}

재귀를 사용하여 단일 연결 목록 뒤집기

struct node *head;
void reverse(struct node *prev , struct node *cur)
{
    if(cur)
    {
        reverse(cur , cur->next);
        cur->next = prev;
    } else 
        head = prev;
}

void main()
{
    //...
    reverse(NULL , head);
    //..
}

순환 연결 목록

순환 연결 목록에는 머리인 센티넬을 가리키는 꼬리가 있지만 첫 번째 요소에 대한 포인터 대신 노드 수를 포함합니다.

while(p->next != head){}

이중 연결 리스트

// insert at start
struct node {
    int i;
    struct node *prev;
    struct node *next;
};
t->next = head;
head = t;
t->prev = NULL;
head->next->prev = head;

// insert at the end
while(p->next) p = p->next;
p->next=t;
t->prev=p;
t->next=NULL;

// insert between > 1 and < n where n is number of node
t->prev=p; // p is the pointer of the element previous to t
t->next=p->next;
p->next=t;
t->next->prev=t;