[자료구조] 연결 리스트(Linked list)와 구현 (1)

연결 리스트(Linked list)

연결 리스트란 데이터(data)와 링크(link)로 구성된 개별의 노드(Node)로 연결되어 있는 자료 구조이다.

연결 리스트

데이터(data)는 정수, 실수, 문자열 등 말 그대로 데이터를 담고 있고, 링크(link)는 다음 노드를 가리키는 포인터이다.

노드(node)는 데이터와 링크로 이루어진 연결 리스트 구성 단위로써, 연결 리스트의 각 노드들은 이 링크로 연결되어진다.

 

연결 리스트의 종류

단순 연결 리스트 

다음 노드에 대한 링크만 가지고 있으며, 한쪽 방향으로만 순회가 가능하다

 

이중 연결 리스트
이전 노드와 다음 노드에 대한 링크를 가지고 있으며, 양방향 순회가 가능하다

 

원형 연결 리스트

연결 리스트의 마지막 노드 링크가 처음 노드를 가리키도록 구성한 연결 리스트이며, 처음 노드가 다시 나타나면 순회를 멈춘다.

 

 

단순 연결 리스트(Singly linked list)

단순 연결 리스트(singly linked list)는 다음 노드에 대한 링크만 가지고 있으며, 한쪽 방향으로만 순회가 가능한 연결 리스트이다.

 

구현은 다음과 같다.

# include <iostream>

struct Node
{
  int data;
  Node* next;
  // 노드는 data와 Link로 이루어져 있으며,
  // 단순 연결 리스트이기 때문에 다음 노드에 대한 링크만 존재
};

class SinglyLinkedList
{
private:
  // 연결 리스트는 노드로 구성된다.
  Node* head;

public:
  // 단순 연결리스트가 생성될 때, head값에 nullptr 선언
  SinglyLinkedList() : head(nullptr) {};
  
  ~SinglyLinkedList()
  {
    // 연결 리스트가 비어있지 않으면, 빌 때까지 앞에서부터 순차적으로 node삭제 후 소멸자 선언
    // 이 과정을 거치지 않으면, 추가된 node들이 모두 메모리에 남게 되어 메모리 누수 발생
    while (!is_empty())
    {
      pop_front();
    }
  }

  // 연결 리스트 앞에 새로운 node 삽입
  void push_front(int val)
  {
    // val을 data로 가지는 새로운 node 생성
    Node* new_node = new Node {val, NULL};

    // 만약 연결 리스트가 비어있을 경우 (head == nullptr) head 뒤에 추가
    // 비어있지 않으면 새로운 노드를 head와 연결 리스트의 맨 앞 node 사이에 삽입
    if (head != nullptr)
    {
      // 추가되는 new_node의 next(해당 노드가 가리키는 다음 노드)를 
      // head가 가리키고 있는 연결 리스트의 맨 앞 노드로 옮겨준다
      new_node -> next = head;
    }
    
    // head가 가리키는 연결 리스트의 맨 앞 node는 new_node가 된다.
    head = new_node;
  }

  // 연결 리스트 맨 앞 node 삭제
  void pop_front()
  {
     // 만약 연결 리스트가 비어있을 경우 (head == nullptr) 함수 종료
    if (head == nullptr)
    {
      return;
    }
    // 첫 번째 요소를 가리키는 first 포인터 변수 선언
    Node* first = head;
    // head가 가리키는 요소를 head -> next(현재 첫 번째 node가 가리키는 두 번째 node)로 이동
    head = head -> next;
    // 첫 번째 요소 삭제
    delete first;
  }

  // 연결 리스트 데이터 출력
  void print_all()
  {
    // 현재 node를 나타내는 curr 선언
    // 첫 번째 node부터 순회를 시작하기 때문에 head가 가리키는 첫 node로 선언
    Node* curr = head;
    // curr이 맨 마지막 노드를 지나칠때까지 (NULL) 반복
    while(curr != nullptr)
    {
      // 현재 node의 data를 출력하고, 다음 노드로 넘어간다
      std::cout << curr -> data << ",";
      curr = curr -> next;
    }
    std::cout << std::endl;
  }

  // 연결 리스트가 비어있는지 확인
  bool is_empty() const
  {
    // head가 nullptr이면 연결리스트가 비어있다는 뜻
    return head == nullptr;
  }

};

단순 연결 리스트의 장, 단점

단순 연결 리스트의 장점

임의의 위치에 원소의 삽입 삭제가 O(1)의 시간복잡도를 가지므로 효울적이다

크기 제한이 없다

 

단순 연결 리스트의 단점

임의의 원소에 대한 접근이 O(N)의 시간복잡도를 가진다

data 외에 link를 위한 여분의 메모리 공간을 사용한다