[Data Structure] Linked List

연결리스트란?

• 연속된 메모리 위치에 저장되지 않는 선형 데이터 구조
  • 포인터를 사용해서 연결된다.
• Linked List는 컴퓨터 과학에서 사용하는 기본적인 선형 자료 구조 중 하나
• 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성
  • Linked List는 데이터의 동적 추가, 삭제를 상대적으로 쉽게 할 수 있는 장점이 있다.
• Linked List의 핵심 요소는 다음과 같다.
  • 노드(Node) : Linked List의 기본 단위, 데이터를 저장하는 필드와 다음 노드를 가리키는 링크 필드로 구성
  • 포인터 : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
  • 헤드(Head) : Linked List에서 가장 처음 위치하는 노드. 리스트 전체를 참조하는데 사용
  • 테일(Tail) : Linked List에서 가장 마지막에 위치하는 노드. 이 노드의 링크 필드는 NULL을 가리킴

연결 리스트의 종류

• 연결 리스트는 다양한 형태로 확장될 수 있다.
• 각 노드가 다음 노드를 참조하고 마지막 노드는 NULL을 참조하는 단순 연결 리스트(Single Linked List)
• 각 노드가 이전 노드와 다음 노드를 모두 참조하는 양방향 리스트(Doubly Linked List)
• 마지막 노드가 처음 노드를 참조하는 원형 연결 리스트(Circular Linked List)

연결리스트를 사용하는 이유

배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음

1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함
2. 새로운 요소를 삽입하는 것은 비용이 많이 듬 (공간을 만들고, 기존 요소 전부 이동)

장단점

장점

• 리스트의 크기를 동적으로 할당할 수 있다.
• 삽입과 삭제에 용의하다

단점

• 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 (이진 검색 수행 불가능)
• 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요

연결 리스트 구현

노드 구현

// A linked list node 
typedef struct Node{
    int data;
    struct Node* next;
    Node(int data){
        this->data = data; next = NULL;
    }
}Node;

Single Linked List

• 3개의 노드를 잇는 코드

#include <iostream>
using namespace std;

typedef struct Node{
    int data;
    struct Node* next;
    Node(int data){
        this->data = data; next = NULL;
    }
}Node;

Node* head;

void printList(){
    Node* n = head;
    while(n){
        cout<<n->data<<" ";
        n = n->next;
    }
}

int main(){
    head = new Node(1);
    Node* second = new Node(2);
    Node* thired = new Node(3);

    /*
          llist.head        second              third 
             |                |                  | 
             |                |                  | 
         +----+------+     +----+------+     +----+------+ 
         | 1  | null |     | 2  | null |     |  3 | null | 
         +----+------+     +----+------+     +----+------+ 
    */

    head->next = second;
    second->next = thired;

    /*
          llist.head        second              third 
             |                |                  | 
             |                |                  | 
         +----+------+     +----+------+     +----+------+ 
         | 1  | null |     | 2  | null |     |  3 | null | 
         +----+------+     +----+------+     +----+------+ 
    */
       
    printList();
}

노드 추가

앞쪽에 노드 추가

void push(int data){
    Node* new_node = new Node(data);
    new_node->next = head;
    head = new_node;
}

특정 노드 다음에 추가

void insertAfter(Node* prev, int data){
    if(!prev){
        cout<<"The given previous node cannot be null"<<'\n';
        return;
    }
    
    Node* new_node = new Node(data);
    new_node->next = prev->next;
    prev->next = new_node;
}

끝쪽에 노드 추가

void append(int data){
    Node* new_node = new Node(data);

    if(!head){
        head = new Node(data);
        return;
    }
    
    new_node->next = NULL;

    Node* last = head;
    while(last->next)
        last = last->next;
    
    last->next = new_node;
}

전체 코드

#include <iostream>
using namespace std;

typedef struct Node{
    int data;
    struct Node* next;
    Node(int data){
        this->data = data; next = NULL;
    }
}Node;

Node* head;

void push(int data){
    Node* new_node = new Node(data);
    new_node->next = head;
    head = new_node;
}

void insertAfter(Node* prev, int data){
    if(!prev){
        cout<<"The given previous node cannot be null"<<'\n';
        return;
    }
    
    Node* new_node = new Node(data);
    new_node->next = prev->next;
    prev->next = new_node;
}

void append(int data){
    Node* new_node = new Node(data);

    if(!head){
        head = new Node(data);
        return;
    }
    
    new_node->next = NULL;

    Node* last = head;
    while(last->next)
        last = last->next;
    
    last->next = new_node;
}

void printList(){
    Node* n = head;
    while(n){
        cout<<n->data<<" ";
        n = n->next;
    }
}

int main(){
    // 6->NULL
    append(6);
    
    // 7->6->NULL
    push(7);
    
    // 1->7->6->NULL
    push(1);

    // 1->7->6->4->NULL
    append(4);
    
    // 1->7->8->6->4->NULL
    insertAfter(head->next,8);
    
    cout<<"\ncreated Linked List is : ";
    printList();
}

 

 

 

출처

https://velog.io/@hyhy9501/5-1-Linked-List-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4

1-5. [자료구조이론] Linked List (연결 리스트)

https://github.com/gyoogle/tech-interview-for-developer/tree/master

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖