링크드 리스트, STL list

msung99·2022년 3월 6일
알고리즘
0
post-thumbnail

연결리스트의 특징

  • k번째 원소를 확인/변경 : O(k)
  • 임의의 위치의 원소를 추가/제거 : O(1)
  • 원소들이 메모리 상에 연속해있지 않아 Cache hit rate 가 낮지만 할당이 다소 쉬움

연결리스트의 종류

  • 단일 연결 리스트(Singly 링크드 리스트)
  • 이중 연결 리스트(Doubly 링크드 리스트)
  • 원형 연결 리스트(Circular Linked list) : 끝이 처음과 연결되어있음.

시간 복잡도 정리 (배열 vs 연결 리스트)

  • k번째 원소의 접근 : 배열 - O(1) // 연결리스트 - O(k)

  • 임의의 원소 추가/제거 : 배열 - O(n) // 연결리스트 - O(1)

  • 메모리 상의 배치 : 배열 - 연속적으로 배치 // 연결리스트 - 불연속적으로 배치

  • 추가적으로 필요한 공간 : 배열 - x(추가공간 필요없음) // 연결리스트 - O(n)

각 기능의 시간 복잡도 분석

  1. 임의의 위치에 있는 원소를 확인/변경 : O(n)
  • 배열과 달리 임의의 위치에 있는 원소에 가기위해선 첫번째 원소부터 순차적으로 방문해야함 (첫번째 원소의 주소만 알고 있기때문)

13 -> 65 -> 21 -> 17 -> 42
에서 4번째 원소에 접근하기 위해서 13,65,21,17 순서대로 방문해야함

  1. 임의의 위치에 원소를 추가 : O(1)

13 -> 65 -> 21 -> 17 -> 42
에서 21 뒤에 84를 추가하고 싶은 경우 21은 84를 가리키고, 84는 17을 가리키게 하면 된다.
13 -> 65 -> 21 -> 84 -> 17 -> 42

=> * 만일 21의 주소를 준 것이 아니라, 그냥 84라는 원소를 3번째 원소뒤에 추가하라는 명령의 경우에는, 3번째 원소까지 찾아가는 하는 시간이 추가로 걸려서 O(n)이 걸린다!!

3, 임의의 위치의 원소를 제거 : O(1)

13 -> 65 -> 21 -> 17 -> 42
에서 원소 17을 제거하는 경우, 21 은 42를 가리키면 끝이다.

list : STL의 연결리스트

  • STL에 연결 리스트가 있는데, 이 컨테이너의 이름은 list이다.
  • 구조는 더블리 링크드 리스트이다.
  • 코딩테스트 에서는 STL list를 사용하면 된다.

STL list

  • push_back, pop_back, push_front, pop_front() : O(1)
  • iterator 가 주소역할을 한다.

메소드

1.iterator(반복자)

  • begin() : beginning iterator 를 리턴
  • end() : end iterator 를 리턴

2.추가 및 삭제

  • push_front(a) : 맨 앞에 원소 추가
  • pop_front() : 맨 앞 원소 삭제
  • push_back(a) : 맨 뒤에 원소 추가
  • pop_back() : 맨 뒤 원소 삭제
  • insert(iterator, a) : iterator 가 가리키는 부분 "앞"에 원소 a를 추가
  • erase(iterator) : iterator가 가리키는 부분에 원소를 삭제

3.조회

  • *iterator : iterator 가 가리키는 원소에 접근
  • front() : 첫번째 원소를 리턴
  • back() : 마지막 원소를 리턴

4.기타

  • empty() : 링크드 리스트가 비어있으면 true, 아니면 false 를 리턴
  • size() : 링크드 리스트의 원소들의 수를 리턴

예제1


int main(void)
{
  list<int> L = {1,2};
  list<int>::iterator t = L.begin(); // t는 1를 가리키는 중
  // => auto t = L.begin(); 으로 써도 됌
  
  L.push_front(10) // 10 1 2
  cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
  
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // 10 6 1 2 5 => t가 가리키는 곳 앞에 6을 삽입
  
  t++;  t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 리턴
  
  cout << *t << '\n'; // 5
  for(auto i : L) // 10 6 1 5
    cout << i << ' ';
  
  cout << '\n';
  
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

예제2

int main(void)
{
  list<int> l;
  
  l.push_back(5);
  l.push_back(6);
  l.push_back(7);
  l.push_back(8);
  l.push_back(9);
  l.push_back(10);
  
  l.pop_back();
  
  l.pop_front();
  
  cout << "list front value:" << l.front() << '\n';
  cout << "list end value:" << l.end() << '\n';
  
  cout << "list size:" << l.size() << '\n';
  
  cout << "Is it empty?:" << ( l.empty() ? "YES" : "NO") << '\n';
  
  list<int>::iterator begin_iter = l.begin();
  // auto begin_iter = l.begin() 도 가능(동일한 표현)
  
  list<int>::iterator end_iter = l.end();
  // auto end_ter = l.end() 도 가능(동일한 표현)
  
  begin iter++; // 2번쨰를 가리키는 iterator
  l.insert(begin_iter, 2);
  
  end_iter--; // 마지막 원소를 가리키는 iterator
  l.erase(end_iter);
  
  // iterator: 원소 접근
  cout << "list" << distance(l.begin(), begin_iter) + 1 << "element:" 
  << being_iter << '\n';
}

싱글리 링크드리스트 구현

  1. 노드 struct 구현
struct node{
  int data;
  node* nextNode;
}
  1. 링크드 리스트 클래스
class LinkedList{
  private:
    node* head;
    node* tail;
  public:
    LinkedList(){
      // head 와 tail 포인터를 초기화
      head = NULL; 
      tail = NULL;
    }
    
    // 메소드 선언 
    void addFrontNode(int n); // 첫번째의 노드 추가
    void addNode(int n); // 마지막의 노드 추가
    void insertNode(node* prevNode, int n); // 노드 삽입
    void deleteNode(node* prevNode); // 노드 삭제
    void display(node* head); // 링크드리스트 출력
    node* getHead(){ // 첫번째 노드 가져오기 
      return head;
    }   
};

아래에서 각 메소드는 어떻게 구현하면 되는지 알아보자.

싱글리 링크드 리스트 세부구현

  1. 맨 앞에 데이터 추가하기 
// 첫번쨰 노드 추가
void addFrontNode(int n){
  node* temp = new node;
  temp -> data = n; // temp의 데이터는 n
  
  // 링크드 리스트가 비어있으면
  if(head == NULL){
    head = temp; // head와 tail 노드로 temp 를 할당해줌
    tail = temp; 
  }
  
  // 링크드 리스트에 데이터가 있으면
  else{
    temp -> nextNode = head; // temp 의 다음 노드는 head
    head = temp; // head 노드는 이제 temp 가 되어서, 링크드 리스트의 맨 앞 노드가 된다.
  }
}
  1. 맨 끝에 데이터 추가하기
void addNode(int n){
  node* temp = new node;
  
  temp -> data = n; // 
  temp -> nextNode = NULL;
  
  // 빈 링크드리스트인 경우
  if(head == NULL){
    head = temp; // temp 가 head 노드이자 tail 노드가 된다.
    tail = temp;
  }
  
  else{
    tail -> nextNode = temp;
    tail = temp;
  }
}
  1. 데이터 삽입하기
void insertNode(node* prevNode, int n){ // 삽입될 노드의 이전 노드 값 prevNode를 받아옴
  node* temp = new node;
  temp -> data = n;
  
  // 결과적으로 prevNode 는 temp 를 가라키고, temp는 prevNode 의 다음 노드를 가리킴
  // ( prevNode 노드 ==> temp 노드 ==> prevNode->nextNode ) 
  temp -> nextNode = prevNode -> nextNode;
  prevNode -> nextNode = temp;
}
  1. 데이터 삭제하기
void deleteNode(node* prevNode){ // prevNode : 삭제될 노드의 이전노드
  // 결과적으로, prevNode 는 삭제된 노드인 다음노드를 가리키게 됨
  // (기존 링크드 리스트 : prevNode ==> 삭제될 노드 ==> 삭제될 노드의 다음노드)
  // (삭제후 링크드 리스트 : prevNode ==> 삭제될 노드의 다음노드)
  node* temp = prevNode -> nextNode; 
  prevNode -> nextNode = temp -> nextNode;
  
  delete temp; // temp 삭제
}
  1. 데이터 출력하기
void display(node* head){
  if (head == NULL){
    cout << "비었습니다.\n";
  }
  else{
    cout << head -> data << endl;
    display(head->nextNode);
  }
}

싱글리 링크드 리스트 전체 소스코드

#include <iostream>
using namespace std;

struct node{
  int data;
  node* next;
}

class LinkedList{
  private:
    node* head;
    node* tail;
  public:
    LinkedList(){ // 생성자
      head = NULL;
      tail = NULL;
    }
    
    void addFrontNode(int n);
    void addNode(int n);
    void insertNode(node* preNode, int n);
    void deleteNode(node* prevNode);
    
    node* getHead(){
      return head;
    }
    
    void display(node* head);
};

// 맨 앞에 노드추가
void Linkedlist::addFrontNode(int n){
  node* temp = new node;
  temp -> data = n;
  
  if(head -> NULL){
    head = temp;
    tail = temp;
  }
}
  
  else{
    temp -> next = head;
    head = temp;
  }
  
// 맨 뒤에 노드추가
void LinkedList::addNode(int n){
  node* temp = new node;
  temp -> data = n;
    
  if(head == NULL){
    head = temp;
    tail = temp;
  }
  else{
    tail -> next = temp;
    tail = temp;   
  }
}
  
// 노드 삽입
void LinkedList::insertNode(node* prevNode, int n){
  node* temp = new node;
  temp -> data = n;
    
  temp -> next = prevNode -> next;
  prevNode -> next = temp;
}
  
// 노드 삭제
void LinkedList::deleteNode(node* prevNode){
  node* temp = prevNode -> next;
  prevNode->next = temp -> next;
    
  delete temp;
}
  
// 링크드리스트 출력
void LinkedList::display(node* head){
  if(head == NULL){
    cout << "\n";
  }
  else{
    cout << head -> data << " ";
    display(head -> next);
  }
  cout << endl;
}


int main()
{
  LinkedList a;
  
  // 링크드 리스트 끝에 데이터를 십입
  a.addNode(1);
  a.addNode(2);
  a.addNode(3);
  
  cout << "1,2,3을 LinkedList에 추가함\n";
  a.display(a.getHead());
  
  // 0을 링크드 리스트 맨 앞에 추가
  a.addFrontNode(0); 
  
  // 1을 4번째 노드로 만듦
  a.insertNode(a.getHead() -> next -> next, 1);
  cout << "1을 4번째에 추가\n";
  a.display(a.getHead());
  
  // 3번째 노드 삭제
  a.deleteNode(a.getHead() -> nextNode); 
  cout < "3번쨰 노드를 삭제함\n";
  a.display(a.getHead());
}

더블리 링크드 리스트 구현

  1. 노드 클래스
class Node{
  string data; // 문자열 데이터
  Node* prev;
  Node* next;
  friend class DLinkedList;
};
  1. 더블리 링크드리스트 클래스
#include <string>
#include <iostream>

using namespace std;

class Node {
    string strData;
    Node* pStPrev;
    Node* pstNext;
    friend class DLinkedList;
};

class DLinkedList {
    public:
        DLinkedList();  // create empty list
        ~DLinkedList();
        bool isEmpty() const;
        const string& getFront() const;
        const string& getBack() const;
        void addFront(const string& e);
        void addBack(const string& e);
        void removeFront();
        void removeBack();
        void TraverseForward();
        void TraverseBackward();
    private:
        Node* header;
        Node* trailer;
    protected: // local utilities
        void add(Node* v, const string& e);
        void remove(Node* v);
};

DLinkedList::DLinkedList() {
    header = new Node;
    trailer = new Node;

    // Header and Trailer are sentinel Nodes.
    // No data is included at those nodes.
    header->pstNext = trailer;
    trailer->pStPrev = header;
}

DLinkedList::~DLinkedList() {
    while(!isEmpty()) removeFront();
    delete header;
    delete trailer;
}

bool DLinkedList::isEmpty() const {
    if (header->pstNext == trailer);
}

const string& DLinkedList::getFront() const {
    return header->pstNext->strData;
}

const string& DLinkedList::getBack() const {
    return trailer->pStPrev->strData;
}

더블리 링크드 리스트 상세 구현

void DLinkedList::addFront(const string& e) {
    add(header, e);
}

void DLinkedList::addBack(const string& e) {
    add(trailer->pStPrev, e);
}


// Insert new Node after v
void DLinkedList::add(Node* v, const string& e) {
    Node* u = new Node;
    u->strData = e;
    u->pstNext = v->pstNext;
    u->pStPrev = v;

    v->pstNext->pStPrev = u;
    v->pstNext = u;
}


void DLinkedList::removeFront() {
    remove(header->pstNext);
}

void DLinkedList::removeBack() {
    remove(trailer->pStPrev);
}

void DLinkedList::remove(Node* v) {
    Node* u = v->pStPrev;
    Node* w = v->pstNext;
    u->pstNext = w;
    w->pStPrev = u;
    delete v;
}

void DLinkedList::TraverseForward() {
    Node* v = header->pstNext;
    while(v->pstNext != NULL) {
        cout << v->strData << " ";
        v = v->pstNext;
    }
}

void DLinkedList::TraverseBackward() {
    Node* v = trailer->pStPrev;
    while(v->pStPrev != NULL) {
        cout << v->strData << " ";
        v = v->pStPrev;
    }
}

int main (void) {
    DLinkedList* DL = new DLinkedList();

    DL->addFront("3");
    DL->addFront("5");
    DL->addFront("8");
    DL->addFront("10");

    // 3 -> 5 -> 8 -> 10
    DL->TraverseBackward();

    cout << endl;

    // 10 -> 8 -> 5 -> 3
    DL->TraverseForward();

    cout << endl;

    DL->removeBack();
    DL->removeBack();

    // 10 -> 8
    DL->TraverseForward();
    cout << endl;    

    return EXIT_SUCCESS;
}

야매로 구현한 연결 리스트

const int MX = 1000005;
int dat[MX], pre[MX], next[MX]; // dat[i] : i번째 원소의값, 
// pre[i] : i번째 원소에 대해 이전 원소의 인덱스
// next[i] : 다음 원소의 인덱스
// pre나 next의 값이 -1 이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 의미이다.

int unused = 1; // 현재 사용되지 않은 인덱스, 즉 새로운 원소가 들어갈 수 있는 인덱스.
// 원소가 들어간 후에는 1씩 증가한다.

fill(pre, pre + MX, -1);
fill(pre, next + MX, -1);
  • 원소를 배열로 관리하고 pre 와 nxt 이전 / 다음 원소의 포인터 대신 배열상의 인덱스를 저장하는 방식으로 구현한 리스트이다.
    (메모리 누수문제 때문에 실무에서는 안쓰이지만, 코테에서 잘 쓰일수있음)
  • 0번지는 연결 리스트의 시작 원소로 고정되어 있음
    달리말해 0번지는 값이 들어가지 않고 단지 시작점을 나타내기 위한 dummy node 이다.
profile
msung99
블로그 이전했습니다 🙂 : https://haon.blog
이전 포스트

배열 & STL vector

다음 포스트

원형 링크드리스트 (Circular Linked List)

0개의 댓글