SLL(Singly Linked List)

개념

SLL 이란 데이터를 저장하고 있는 노드들이 한 방향으로 연결되어 있는 자료구조이다. 

저장 공간이 한정적인 배열과 달리, 계속해서 데이터들을 추가할 수 있다는 장점이 있다.

또한 데이터의 삽입이 어려운 배열에 비해 중간에 삽입하거나, 데이터를 삭제할 수도 있다. 

 

구현(C/C++)

1. 데이터와 포인터를 담을 구조체 선언

typedef struct node
{
    int i;
    struct node*next;
}node;

 

2. SLL에 데이터 추가

void add(int a)
{
    node* newnode = (node*)malloc(sizeof(node)); //입력받은 수를 데이터로 갖는 노드 생성
    newnode->i=a;
    newnode->next=0;
    
    if(head==0) //SLL이 비어있다.
    {
    	head=newnode;
        return;
    }
    //SLL에 무언가 들어있는 상태
    node *last = head;
    while(last->next!=0) //SLL의 마지막 노드까지 이동
    {
    	last=last->next;
    }
    last->next=newnode; //마지막 노드의 다음이 새로운 노드가 되도록 가리킴.
    return;
}

 

3. SLL에서 데이터 제거

void deleteSLL(int v) //지우려는 값 입력받음.
{
    node*del, *del_next;
    del_next = head;
    if(head->i==v) //지우려는 값이 head라면 head를 옆으로 옮기고 del을 free
    {
    	del=head;
        head=head->next;
        free(del);
        return;
    }
    else
    {
    	while(del_next->next!=0) //지우려는 값을 찾을 때까지 이동하여
        {
        	if(del_next->next->i == v) //찾으면 free(del)
            {
            	del=del_next->next;
                del_next->next=del->next;
                free(del);
                return;
            }
            else
            {
            	del_next = del_next->next;
            }
        }
    }
}

4. SLL의 요소 출력

void printSLL()
{
    node*cur = head;
    while(cur!=0) //SLL의 끝까지 이동하면서 출력
    {
    	cout<<cur->a<<endl;
        cur=cur->next;
    }
}