자료구조 최종정리 : 리스트(단일, 원형)

리스트는 배열 리스트, 포인터 리스트로 구성할 수 있다.

배열리스트 소스

#include<iostream>
#include<conio.h>
#include<string>
#include<vector>

using namespace std;

class ArrayListNode
{
public:
 int data;
};

class ArrayList
{
public:
 int m_MaxElementCount; //최대원소 개수
 int m_CurrentElementCount; //현재 원소 개수
 ArrayListNode* pElement; //원소 저장을 위한 배열 포인터

public:
 ArrayList(){}
 ~ArrayList(){}
 //리스트 생성함수
 void CreateArrayList(int maxElementCount)
 {
  if(maxElementCount>0)
  {
    m_MaxElementCount=maxElementCount;
    m_CurrentElementCount=0;
    pElement=NULL;
  }
  else
  {
   cout <<" 최대원소 개수는 0 이상이 되어야합니다" << endl;
  }
  
  pElement=new ArrayListNode[maxElementCount]; //이건 해제하는데..
  if(pElement==NULL)
  {
   cout<<"오류 원소 메모리할당 오류"<< endl; 
  }
  memset(pElement,0,sizeof((pElement))*maxElementCount);
 }

 bool isArrayListFull()
 {
  bool ret=false;
  if(m_CurrentElementCount==m_MaxElementCount)
  {
   ret=true;
  }
  return ret;
 }

 //배열 리스트 임의의 위치에 원소를 추가..
 bool addALElement(int position, ArrayListNode element)
 {
  bool ret=false;
  int i=0;
  if(isArrayListFull()!=true)
  {
   if(position>=0 && position<=m_CurrentElementCount)
   {
    for(i=m_CurrentElementCount-1;i>=position;--i)
    {
     pElement[i+1]=pElement[i];
    }

    pElement[position]=element;
    m_CurrentElementCount++;
    ret=true;
   }
   else
   {
    cout <<"인덱스 범위 초과"<< endl;
   }
  }  {
   cout<<"리스트 용량 없음"<<endl;
  }
  else

  return ret;
 }

 //기존 원소를 제거하는 함수
 bool removeALElement(int position)
 {
  bool ret=false;
  int i=0;
  if(position>=0 && position<m_CurrentElementCount)
  {
   for(i=position;i<m_CurrentElementCount-1;i++)
   {
    pElement[i]=pElement[i+1];
   }

   m_CurrentElementCount--;
   ret=true;
  }
  else
  {
   cout <<"오류 위치 인덱스 범위초과"<< endl;
  }

  return ret;
 }

 //현재 원소의 길이를 반환(cuurent값)
 int getArrayListLength()
 {
  return m_CurrentElementCount;
 }

 //원소 반환
 ArrayListNode* getALElement(int position)
 {
  ArrayListNode *pReturn=NULL;
  if(position>=0 && position < getArrayListLength())
  {
   pReturn=&pElement[position];
  }
  else
  {
   cout << "오류 위치 인덱스 범위 초과"<<endl;
  }
  return pReturn;
 }

 void displayArrayList()
 {
  int i=0;
  cout << "최대 원소 저장개수 "<< m_MaxElementCount << endl;
  cout << "현재 원소 저장개수 "<< m_CurrentElementCount << endl;

  for(i=0;i<m_CurrentElementCount;i++)
  {
   cout << "["<<i<<"]" << getALElement(i)->data << endl;
  }

  i=m_CurrentElementCount;
  for(;i<m_MaxElementCount;i++)
  {
   cout << "["<<i<<"]" <<"empty" << endl;
  }
 }
 
 //원소 리스트 삭제 왜냐면..pelement만 new했잖아..
 void DeleteArrayList()
 {
  int i=0;
  delete [] pElement;
 }
 
};

int main()
{
 int i=0;
 int arrayCount=0;

 ArrayList *pList=new ArrayList;
 ArrayListNode *pValue=NULL;
 pList->CreateArrayList(6);

 ArrayListNode node;

 node.data=1;
 pList->addALElement(0,node);

 node.data=3;
 pList->addALElement(1,node);

 node.data=5;
 pList->addALElement(2,node);
 pList->displayArrayList();

 pList->removeALElement(0);
 pList->displayArrayList();

 arrayCount=pList->getArrayListLength();

 for(i=0;i<arrayCount;i++)
 {
  pValue=pList->getALElement(i);
  cout << "위치"<< i << " " << pValue->data << endl;
 }

 pList->DeleteArrayList();
 delete pList;
 getch();
 return 0;
}

 

포인터 리스트는 3개로 나뉜다.

1. 단일 연결리스트

2. 원형 연결리스트

3. 이중 연결리스트

 

일단 단일 연결리스트..소스

#include<iostream>
#include<conio.h>
#include<string>
#include<vector>

using namespace std;

//연결리스트에 저장되는 노드를 표현
//데이터와 링크가 있다.
class ListNode
{
public:
 int data;
 ListNode *pLink;
public:
 ListNode()
 {
  data=0;
  pLink=NULL;
  cout <<"listnode 생성"<< endl;
 }
 ~ListNode()
 {
  cout<<"listnode 해제"<<endl;
 }
};

//연결 리스트 구현을 위한 클래스/
class LinkedList
{
public:
 //현재 저장된 개수
 int m_currentElementCount;
 //헤더노드
 /*이 헤더노드는 데이터 저장을 위한 노드가 아니라 노드의 추가/삭제의
 구현의 간편성을 위해 사용하는 일종의 더미노드다.
 실제 데이터를 저장하는 다른 노드를 가리키는 포인터의 역할을 수행ㅔ
 */
 ListNode headerNode; //더미노드가 꼭 객체가 아닌 포인터를 동적할당해도..

public :
 LinkedList()
 {
  m_currentElementCount=0;
  cout <<"linkedlist 생성"<< endl;
 }
 ~LinkedList()
 {
  cout <<"linkedlist 해제"<<endl;
 }
 //연결 리스트 임의의 위치에 새로운 노드가 추가되는 함수
 bool addLLElement(int position, ListNode element)
 {
  bool ret=false;
  int i=0;
  ListNode *pPreNode=NULL;
  ListNode *pNewNode=NULL;
  if(position >= 0 && position <=m_currentElementCount)
  {
   pNewNode=new ListNode;
   if(pNewNode!=NULL)
   {
    *pNewNode=element;
    pNewNode->pLink=NULL;

    //여기서 pprenode는 추가하려는(position)노드의 위치의 이전노드가 된다.
    pPreNode=&(headerNode); 

    for(i=0;i<position;i++)
    {
     pPreNode=pPreNode->pLink;
    }
    
    pNewNode->pLink=pPreNode->pLink;
    pPreNode->pLink=pNewNode;

    m_currentElementCount++;
    ret=true;

   }
   else
   {
    cout <<"메모리 할당 오류"<< endl;
   }
  }
  return ret;
 }
 
 int getLinkedListLength()
 {
  return m_currentElementCount;
 }

 //리스트내 삭제하려는 함수
 bool removeLLElement(int position)
 {
  bool ret=false;
  int i=0;
  int arrayCount=0;
  ListNode *pNode=NULL;
  ListNode *pDelNode=NULL;
  
  arrayCount=getLinkedListLength();
  if(position >=0 && position < arrayCount)
  {
   //삭제하려는 위치(position)의 이전 노드 위치로 이동한다.
   //헤더노드를 시작으로 position-1값만큼 이동
   pNode=&(headerNode);
   for(i=0;i<position;i++)
   {
    pNode=pNode->pLink;
   }

   //링크 재설정
   pDelNode=pNode->pLink;
   pNode->pLink=pDelNode->pLink;
   delete pDelNode;

   m_currentElementCount--;
   ret=true;
  }
  return ret;
 }

 //해당 위치의 노드반환
 ListNode* getLLElement(int position)
 {
  ListNode *pReturn=NULL;
  int i=0;
  ListNode *pNode=NULL;
  if(position >= 0 && position < m_currentElementCount)
  {
   //삭제와 추가함수와 다른점은 i<=position 즉, position까지 찾는다.
   pNode=&(headerNode);
   for(i=0;i<=position;i++)
   {
    pNode=pNode->pLink;
   }
   pReturn=pNode;
  }
  return pReturn;
 }

 void deleteLinkedList()
 {
  ListNode *DelNode=NULL;
  ListNode *DelNextNode=NULL;

  DelNode=&(headerNode);
  if(DelNode->pLink!=NULL)
  {
   DelNode=DelNode->pLink;
   DelNextNode=DelNode->pLink;
   
   for(int i=0;i<m_currentElementCount;i++)
   {
    cout << i << "번째 노드 삭제입니다."<< endl;
    if(DelNextNode->pLink!=NULL)
    {
     delete DelNode;
     DelNode=DelNextNode;
     DelNextNode=DelNode->pLink;
    }
    else
    {
     delete DelNextNode;
     }
   }
  }
 }
 void displayLinkedList()
 {
  int i=0;
  cout << "현재 원소 개수: " << m_currentElementCount << endl;
  for(i=0;i<m_currentElementCount;i++)
  {
   cout << "["<< i <<"]"<<getLLElement(i)->data << endl;
  }
 }
};

int main()
{
 int i=0;
 int arrayCount=0;
 LinkedList *pList=new LinkedList;
 //ListNode *pNode=NULL;
 ListNode node;

 node.data=1;
 pList->addLLElement(0,node);

 node.data=3;
 pList->addLLElement(1,node);

 node.data=5;
 pList->addLLElement(2,node);
 cout << endl;
 pList->displayLinkedList();

 pList->removeLLElement(0);
 cout << endl;

 pList->displayLinkedList();

 pList->deleteLinkedList();

 cout << endl;
 cout << "리스트를 삭제합니다"<< endl;
 delete pList;
 getch();
 return 0;
}

초록색 글씨는 전체삭제 함수가 없어서 만든것

 

단일 연결리스트는 헤드노드를 이용해서 만든것이고

밑에 이제 원형리스트의 경우 헤드포인터를 이용해서 만들 예정인데..헤드포인터의 경우 더 만들기 어렵다

더미 노드를 하나 만듬으로써, 어느곳에 추가하여도 더미가 없는 것에서의

중간에서 추가하는 논리와 같아진다? 이게 뭔말이지...

 

더미노드라고 해서..위에 단순 연결처럼 객체가 아닌..

포인터를 동적할당해서 더미노드로 활용해도 될것같다..

..

아..아 정리하면 말이다...

더미노드가 없으면... 노드를 추가 삭제 그리고 조회하는 방법에 있어서 첫 번쨰 노드와 두번 째 이후의 노드에 차이가 있다.

(왜냐면...모르잖아 이게 첨인지 중간인지..젠장..ㅠ아닌가)

하지만 더미노드가 생기면 처음추가되는 노드가 구조상 두번 째 노드가 되니까.. 노드의 추가 삭제 및 조회의 과정을 일관되게 구현할 수 있다.

노드를 추가 시킬때

더미가 있다면

새로운 노드는 head가 가리키는 노드를 가리키고 head는 새로운 노드를 가리키면 된다.

newnode->next=head->next

head->next=newnode

 

하지만 더미노드가 없으면..head는 평상시 null을 품고 있다가..

새로운 노드를 처음 추가될때는 그냥 head가 새로운노드를 품으면 된다.

head=newnode;

 

그 다음에 추가할때가 달라질텐데..(두번쨰부터는..)

head는 기존 노드를 품고 있으니까 새로운 노드는 head가 품었던 노드를 가리키고

newnode->next=head;

head는 새로운 노드를 품어야 한다.

head=newnode;

따라서 연결리스트가 비어있을때와 추가될떄가 다르다..그래서 따로 처리해야한다..

 

아아..품는다와 가리키다는 분명히 다르다 여기서

품는다는

head=newnode를 말하고

가리키다는

head->next=newnode다

아아...이해가 조금되었다..

 

원형 리스트

#include<iostream>
#include<conio.h>
#include<string>
#include<vector>

using namespace std;

class CircularListNode
{
public:
 int data;
 CircularListNode *pLink;
};

class CircularList
{
public:
 int m_currentElementCount; //현재 저장된 원소의 개수
 CircularListNode *pLink; //헤드포인터로 구성
public:
 bool addCLElement(int position, CircularListNode element)
 {
  bool ret=false;
  int i=0;
  CircularListNode *pPreNode=NULL, *pNewNode=NULL, *pLastNode=NULL;
  if(position >=0 && position <= m_currentElementCount)
  {
   pNewNode=new CircularListNode;
   if(pNewNode==NULL)
   {
    cout << "메모리 하당오류"<<endl;
    return ret;
   }
   *pNewNode=element;
   pNewNode->pLink=NULL;

   if(position==0)
   {
    if(m_currentElementCount==0)
    {
     //1. 공백 리스트에서 첫 번째 노드를 추가하는 경우
     pLink=pNewNode;
     pNewNode->pLink=pNewNode;
    }
    else
    {
     //2. 공백 리스트가 아닌 원형 연결 리스트에서 첫 번째 노드를 추가하는 경우
     pLastNode=pLink;
     while(pLastNode->pLink!=pLink)
     {
      pLastNode=pLastNode->pLink;
     }
     pLink=pNewNode;
     pNewNode->pLink=pLastNode->pLink;
     pLastNode->pLink=pNewNode;
    }
   }
   //3. 중간에 노드를 추가하는 경우
   else
   {
    pPreNode=pLink;
    for(i=0;i<position;i++)
    {
     pPreNode=pPreNode->pLink;
    }
    
    pNewNode->pLink=pPreNode->pLink;
    pPreNode->pLink=pNewNode;
   }

   m_currentElementCount++;
   ret=true;
  }
  return ret;
 }
 
 int getCircularListLength()
 {
  return m_currentElementCount;
 }

 bool removeCLElement(int position)
 {
  bool ret=false;
  int i=0, arrayCount=0;
  CircularListNode *pPreNode=NULL, *pDelNode=NULL, *pLastNode=NULL;
  arrayCount=getCircularListLength();
  if(position>=0 && position < arrayCount)
  {
   if(position==0)
   {
    pDelNode=pLink;

    //1. 마지막 노드이면서 동시에 첫 번째 노드를 제거하는 경우
    if(arrayCount==1)
    {
     delete pDelNode;
     pLink=NULL;
    }
    //2. 마지막 노드가 아닌 첫번쨰 노드를 제거하는 경우
    else
    {
     pLastNode=pLink;
     while(pLastNode->pLink!=pLink)
     {
      pLastNode=pLastNode->pLink;
     }
     pLastNode->pLink=pDelNode->pLink;
     pLink=pDelNode->pLink;
     delete pDelNode;
    }
   }
   //3. 리스트의 중간 노드를 삭제하는 경우
   else
   {
    pPreNode=pLink;
    for(i=0;i<position-1;i++)
    {
     pPreNode=pPreNode->pLink;
    }

    pDelNode=pPreNode->pLink;
    pPreNode->pLink=pDelNode->pLink;
    delete pDelNode;
   }
   m_currentElementCount--;
   ret=true;
  }
  return ret;
 }
  
};

int main()
{

 getch();
 return 0;
}

 

내용상에 틀린점이 있으면..말해주세요..다시보니..저도 이해가 될듯 말듯하네요..