연결리스트 구현하기 in C++

연결리스트란?

• 연결리스트(Linked List)이란 여러 자료구조 중 하나로, 하나의 노드가 다음 노드를 계속 가리키는 구조이다.
  예를 들어보면 우리가 [2, 4, 3, 7, 8]을 순서대로 스택에 삽입하면, 2를 가진 노드는 다음 노드로 4를 가리키고, 4를 가진 노드는 다음 노드로 3을 가리키는 것이다.
  
  
• 아주 쉽게 설명하면, 만화나 드라마의 ‘다음회에 계속…‘이 그 예가 되겠다.
  우리가 예를 들어 드라마 1회를 본 다음, 드라마 끝에서 ‘다음회에 계속…‘이라는 문구르 보면, 당연히 다음 회차인 2회를 나타낸다고 생각하기 때문이다.

코드 소개

• C++언어를 이용하여 연결리스트를 구현해보는 프로그램이다.

코드

• List.h

/*
 * List.h
 *
 *  Created on: 2017. 4. 15.
 *      Author: Minsu
 */

#ifndef LIST_H_
#define LIST_H_

#include "Node.h"
using namespace std;

typedef string ItemType;

class List
{
    int length; // Size of list
    Node* head;
    bool isFull() const; // Is list full?
    int findLoc(ItemType value) const; // return element(which value is 'ItemType value')'s position in list

public:
    List(); // Constructor
    ~List(); // Destructor

    void insert(ItemType value); // add element in list
    void remove(ItemType value); // delete element which value is 'ItemType value'
    void print(); // print all elements in list(ascending sort)
    int size() const; // return list's size
};

#endif /* LIST_H_ */

• List.cpp

/*
 *List.cpp
 *
 * Created on: 2017. 4. 15.
 *     Author: Minsu
 */

#include <iostream>
#include "List.h"
using namespace std;

typedef string ItemType;

List :: List()
{ // Constructor
    length = 0; // list's initial size is 0
    head = NULL;
}

List :: ~List()
{ // Destructor
    Node *tmpPtr = NULL;

    while(head != NULL)
    {
        tmpPtr = head;
        head = head->next;
        delete tmpPtr;
    }
}

bool List::isFull() const
{ // Is list full?
    Node *location;

    try
    {
        location = new Node;
        delete location;
        return false;
    }
    catch(std::bad_alloc exception)
    {
        return true;
    }
}

void List :: insert(ItemType value)
{ // add element in list
    if(isFull())
    { // List is full
        cout << "Error: the list is full." << endl;
    }
    else
    { // List isn't full
        Node *tmpPtr;
        tmpPtr = new Node;

        tmpPtr->info = value;
        tmpPtr->next = head;

        head = tmpPtr;

        length++; // increase list's size
    }
}

void List :: remove(ItemType value)
{ // delete element which value is 'ItemType value'
    Node *location;

    if(findLoc(value) == 1)
    { // if element is first-node
        location = head;
        head = head->next;
    }
    else
    { // if element isn't first-node
        Node *predLoc = head;

        for(int i = 1; i < findLoc(value) - 1; i++)
        { // connect nodes(before node which have element('value')) to each's next nodes
            predLoc = predLoc->next;
        }

        location = predLoc->next;
        predLoc->next = location -> next;
    }

    length--; // decrease list's size
    delete location;
}

void List :: print()
{ // print all elements in list(ascending sort)
    Node *a = head;
    Node *b;
    string tmp;
    Node *tmpPtr = head;

    for(a = head; a != NULL; a = a->next)
    { // ascending sort
        for(b = a->next; b != NULL; b = b->next)
        {
            if(a->info > b->info)
            { // Swap
                tmp = a->info;
                a->info = b->info;
                b->info = tmp;
            }
        }
    }

    while(tmpPtr != NULL)
    { // repeat from start to end
        cout << tmpPtr->info << " ";
        tmpPtr = tmpPtr->next;
    }

    cout << endl;
}

int List :: findLoc(ItemType value) const
{ // return element(which value is 'ItemType value')'s position in list
    Node *location = head;
    int position = 1; // start position is 1

    while(location != NULL)
    { // repeat from start to end
        if(location->info == value)
        { // if you success in find
            break;
        }
        else
        {
            location = location->next;
            position++; // increase position
        }
    }

    if(location != NULL)
    { // if you success in find
        return position;
    }
    else
    {
        return -1;
    }
}

int List :: size() const
{ // return list's size
    return length;
}