• 연결리스트(Linked List)는 객체의 집합으로 정의할 수 있습니다. 노드 메모리에 무작위로 저장됩니다.
• 노드에는 두 개의 필드, 즉 특정 주소에 저장된 데이터와 메모리의 다음 노드 주소를 포함하는 포인터가 포함됩니다.
• 목록의 마지막 노드에는 null에 대한 포인터가 포함되어 있습니다.

연결리스트의 용도

• 목록이 메모리에 연속적으로 존재할 필요는 없습니다. 노드는 메모리의 어느 위치에나 상주할 수 있으며 서로 연결되어 목록을 만들 수 있습니다. 이를 통해 공간 활용이 최적화됩니다.
• 목록 크기는 메모리 크기로 제한되므로 미리 선언할 필요가 없습니다.
• 연결리스트에는 빈 노드가 존재할 수 없습니다.
• 단일 연결 리스트에는 기본 유형이나 객체의 값을 저장할 수 있습니다.

배열 대신 연결리스트를 사용하는 이유는 무엇입니까?

지금까지 우리는 배열 데이터 구조를 사용하여 메모리에 개별적으로 저장될 요소 그룹을 구성했습니다. 그러나 Array에는 프로그램 전체에서 사용될 데이터 구조를 결정하기 위해 알아야 할 몇 가지 장점과 단점이 있습니다.

어레이에는 다음과 같은 제한사항이 있습니다.

1. 프로그램에서 배열을 사용하기 전에 배열의 크기를 미리 알아야 합니다.
2. 어레이의 크기를 늘리는 데에는 시간이 많이 걸립니다. 런타임 시 배열 크기를 확장하는 것은 거의 불가능합니다.
3. 배열의 모든 요소는 메모리에 연속적으로 저장되어야 합니다. 배열에 요소를 삽입하려면 모든 이전 요소를 이동해야 합니다.

연결리스트(Linked List)는 배열의 한계를 모두 극복할 수 있는 자료구조이다. 연결리스트를 사용하는 것은 다음과 같은 이유로 유용합니다.

자바의 삽입 정렬

1. 동적으로 메모리를 할당합니다. 연결리스트의 모든 노드는 메모리에 비연속적으로 저장되며 포인터의 도움으로 함께 연결됩니다.
2. 선언 시 크기를 정의할 필요가 없으므로 크기 조정은 더 이상 문제가 되지 않습니다. 목록은 프로그램의 요구에 따라 늘어나고 사용 가능한 메모리 공간으로 제한됩니다.

단일 연결 목록 또는 단방향 체인

단일 연결 리스트는 순서가 지정된 요소 집합의 모음으로 정의할 수 있습니다. 요소의 수는 프로그램의 필요에 따라 달라질 수 있습니다. 단일 연결 리스트의 노드는 데이터 부분과 링크 부분의 두 부분으로 구성됩니다. 노드의 데이터 부분에는 해당 노드가 나타낼 실제 정보가 저장되고, 노드의 링크 부분에는 바로 다음 노드의 주소가 저장됩니다.

자바 배열에 추가

단방향 체인 또는 단일 연결 목록은 한 방향으로만 탐색할 수 있습니다. 즉, 각 노드에는 다음 포인터만 포함되어 있으므로 목록을 반대 방향으로 탐색할 수 없습니다.

그림과 같이 학생이 3개 과목에서 얻은 성적을 연결리스트에 저장하는 예를 생각해 보세요.

위 그림에서 화살표는 링크를 나타냅니다. 모든 노드의 데이터 부분에는 학생이 다른 과목에서 얻은 점수가 포함되어 있습니다. 목록의 마지막 노드는 마지막 노드의 주소 부분에 있는 널 포인터로 식별됩니다. 목록의 데이터 부분에는 필요한 만큼의 요소를 가질 수 있습니다.

복잡성

단일 연결 목록의 작업

단일 연결 리스트에서는 다양한 작업을 수행할 수 있습니다. 이러한 모든 작업의 ​​목록은 아래에 나와 있습니다.

자바의 링크리스트

노드 생성

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

삽입

단일 연결 리스트에 대한 삽입은 다른 위치에서 수행될 수 있습니다. 삽입되는 새로운 노드의 위치에 따라 삽입은 다음과 같은 범주로 분류됩니다.

삭제 및 순회

단일 연결 리스트의 노드 삭제는 다른 위치에서 수행될 수 있습니다. 삭제되는 노드의 위치에 따라 동작은 다음과 같이 분류됩니다.

C의 연결 목록: 메뉴 기반 프로그램

 #include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('

*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
 5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
 Enter the location of the node after which you want to perform deletion 
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } 

산출:

 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9