c++로 작성한 링크드 리스트

자료구조 프로그래밍 과목을 배우면서 c++로 작성한 링크드 리스트입니다.

list.h

#include <iostream>

using namespace std;

 

struct Node

{

        int data;

        Node *link;

        Node(int d = 0, Node *l = 0) :data(d), link(l)

        {

        }

};

 

struct IntList

{

        Node *first; //첫 노드를 가리킴

        Node *last; //마지막 노드를 가리킴

        IntList()

        {

               last = first = 0;

        }

        void Push_Back(int); //리스트 뒤에 삽입

        void Push_Front(int); //리스트 앞에 삽입

        void Insert(int); //정렬되어 있다는 가정 하에

        void Delete(int); //리스트의 원소 삭제

        bool Find(int); //리스트의 원소 탐색

};

ostream &operator<<(ostream &, IntList&);

list.cpp

#include <iostream>

#include "list.h"

 

void IntList::Push_Back(int e)

{

        if (!first) //리스트 존재하지 않을때

               first = last = new Node(e);

        else

        {

               //뒤에 추가

               last->link = new Node(e);

               last = last->link;

        }

}

 

void IntList::Push_Front(int e)

{

        if (!first)

               first = last = new Node(e);

        else

        {

               //앞에 추가

               Node *temp = new Node(e);

               temp->link = first;

               first = temp;

        }

}

 

bool IntList::Find(int e) //중복된 노드 있는지 찾아주는 함수

{

        if (!first)

               return false;

        else

        {

               Node *find = first;

               while (find)

               {

                       if (find->data == e)

                              return true;

                       find = find->link;

               }

               return false;

        }

}

 

void IntList::Insert(int e)

{

        if (Find(e)) //중복된 데이터 있으면 return

               return;

        if (!first)

        {

               first = last = new Node(e);

        }

        else if (first->data > e) //첫번째 데이터가 삽입하는 데이터보다 클 경우

        {

               Node *temp = new Node(e);

               temp->link = first;

               first = temp;

        }

        else if (first->data < e) //첫번쨰 데이터가 삽입하는 데이터보다 작을 경우

        {

               Node *search = first->link;

               while (search->link && search->link->data < e)

                       search = search->link;

               if (!search) //끝에 도달했다면

               {

                       //끝에 삽입

                       Node *temp = new Node(e);

                       last->link = temp;

                       last = temp;

               }

               else

               {

                       //중간에 삽입

                       Node *temp = new Node(e);

                       temp->link = search->link;

                       search->link = temp;

               }

        }

}

 

void IntList::Delete(int e)

{

        if (first->data == e) //첫번째 데이터를 삭제한다면

        {

               //first 위치만 변경

               Node *del = first;

               first = first->link;

               delete del;

        }

        else

        {

               //그 외에는 그 전 노드의 위치까지 기억해야하므로 before, current

               Node *before = first;

               Node *current = first->link;

               while (current)

               {

                       if (current->data == e) //삭제할 데이터 찾았다면

                       {

                              before->link = current->link; //before와 current->link를 연결

                              delete current;

                              return;

                       }

                       //데이터를 찾지 못했다면 before와 current 한칸씩 옮김

                       before = current;

                       current = current->link;

               }

               return;

        }

}

 

ostream &operator<<(ostream &os, IntList &il)

{

        Node *ptr = il.first;

        while (ptr != 0)

        {

               os << ptr->data << " ";

               ptr = ptr->link;

        }

        os << endl;

        return os;

}

 

hw7.cpp

#include <iostream>

#include "list.h"

 

int main(void)

{

        IntList il;

        il.Push_Back(5);

        il.Push_Back(7);

        il.Push_Back(9);

        cout << il;

        il.Push_Front(4);

        il.Push_Front(3);

        cout << il;

        il.Insert(6);

        il.Insert(10);

        il.Insert(2);

        il.Insert(5);

        il.Insert(2);

        il.Insert(10);

        cout << il;

        il.Delete(6);

        il.Delete(10);

        il.Delete(2);

        cout << il;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~