1. ๋ฆฌ์คํธ ¶
- ๋ฆฌ์คํธ๋ ๋ฌด์์ธ๊ณ ํ๋... ์ ์ฅํ๊ณ ์ถ์ ๋ฐ์ดํฐ์ ๋ค์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ๋ฅดํค๋ ํฌ์ธํฐ๋ฅผ ๊ตฌ์กฐ์ฒด๋ก ๋ฌถ์ ๋
ธ๋๋ฅผ ๊ธฐ๋ณธ์ผ๋ก ํด์ ๋ง~ ์ฐ๊ฒฐ์์ผ์ค ๊ฒ์ด๋ค.
~cpp struct Node // ์ ๊ฐ c๋ฌธ๋ฒ์ ์ ๋ชจ๋ฆ ๋๋ค.. ์ฑ ์์๋ typedef์ธ๊ฐ? ์ด์ํ๊ฑธ ์ฐ๋๊ตฐ์. { int lalala; // ๋ฃ๊ณ ์ถ์ ๋ฐ์ดํฐ Node* Next_ptr; // ๋ค์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ๋ฅดํค๋ ํฌ์ธํฐ };
c ๋ฌธ๋ฒ์ผ๋ก ํ๋ฉด.
~cpp typedef struct { int data; Node * link; } Node;
- ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ๋ ๊ฐ๋จํ ์
~cpp ... Node* kkk=new Node; // ๋์ ์์ฑ kkk->lalala=100; // kkk์ ๋ฉค๋ฒ lalala์ 100์ ๋ฃ์. Node* hhh=new Node; // ์๋กญ๊ฒ ๋์ ์์ฑ kkk->Next_ptr=hhh; // kkk์ ๋ฉค๋ฒ Next_ptr์ด ๋ค์ ๋ ธ๋์ธ hhh๋ฅผ ๊ฐ๋ฅดํค๊ฒ ํจ hhh->lalala=50; // hhh์ ๋ฐ์ดํฐ ๋ฃ์ hhh->Next_ptr=NULL; // hhh๋ค์ ์๋ฌด๊ฒ๋ ์์ผ๋ ๋ค์ ๋ ธ๋๋ฅผ ๊ฐ๋ฅดํค๋ ํฌ์ธํฐ๋ฅผ NULL๋ก ์ค์ ํจ ... ... delete kkk; // new๋ก ํ๊ฑด ๊ผญ delete๋ก ์ง์์ฃผ์ delete hhh;
- ์์ ๊ฐ์ด ๋ค์ ๋๋ ๋จผ์ ๋ฒ ๋
ธ๋๋ฅผ ๊ฐ๋ฅดํค๋ ํฌ์ธํฐ๊ฐ ํ๋๋ง ์๋ ๊ฒ์ Single Linked List๋ผ๊ณ ํ๋ค.
- ๋ฐ๋ฉด์ ๋ ๋ค ์๋ ๊ฒ์ Double Linked List๋ผ ํ๋ค.
- Single Linked List์์๋ ํ ์ชฝ์ผ๋ก๋ง ์ด๋์ด ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์ ๋ฉ๋ฆฌ ์๋ ๋
ธ๋๋ฅผ ์ฐพ์๊ฐ๋๋ฐ์ ์๊ฐ์ด ์ข ์ค๋๊ฑธ๋ฆฐ๋ค.
- ์ด๋ฅผ ๋ณด์ํ๊ธฐ ์ํด ๋์จ ๊ฒ์ด Double Linked List์ด๋ค.
- Double Linked List์์๋ ๋งจ ๋ง์ง๋ง ๋
ธ๋์ ๋ค์ ๋
ธ๋๊ฐ NULL์ด ์๋ ๋งจ ์ฒ์ ๋
ธ๋๋ฅผ ๊ฐ๋ฅดํจ๋ค.
- ๋ง์ฐฌ๊ฐ์ง๋ก ๋งจ ์ฒ์ ๋
ธ๋์ ์ ๋
ธ๋๋ ๋งจ ๋ง์ง๋ง ๋
ธ๋๊ฐ ๋๋ค.
- ๊ฒฐ๋ก ์ ์ผ๋ก Single์ ์ฒด์ธ๋ชจ์ Double์ ๊ณ ๋ฆฌ๋ชจ์์ด ๋๋ค.
- Double Linked List๋ฅผ ์ฌ์ฉํ ๊ฐ๋จํ ์(3๊ฐ์ ๋
ธ๋๋ฅผ ์๋ก ๋ฌ)
~cpp struct Node { int lalala; Node* Next_ptr; Node* Prev_ptr; }; ... Node* Head=new Node; // 1 ๋ ธ๋ ๋์ ์์ฑ Node* Mid=new Node; // 2 ๋ ธ๋ ๋์ ์์ฑ Node* Tail=new Node; // 3 ๋ ธ๋ ๋์ ์์ฑ Head->Next_ptr=Mid; // 1 ๋ ธ๋์ ๋ค์ ๋ ธ๋๋ 2๋ ธ๋ Mid->Next_ptr=Tail; // 2 ๋ ธ๋์ ๋ค์ ๋ ธ๋๋ 3๋ ธ๋ Tail->Next_ptr=Head; // 3 ๋ ธ๋์ ๋ค์ ๋ ธ๋๋ 1๋ ธ๋ Head->Prev_ptr=Tail; // 1 ๋ ธ๋์ ์ ๋ ธ๋๋ 3๋ ธ๋ Mid->Prev_ptr=Head; // 2 ๋ ธ๋์ ์ ๋ ธ๋๋ 1๋ ธ๋ Tail->Prev_ptr=Mid; // 3 ๋ ธ๋์ ์ ๋ ธ๋๋ 2๋ ธ๋ ...
- ์ฅ์ : ๋น ๋ฅด๋ค. (๋ฐฐ์ด ๊ฐ์ ๊ฒฝ์ฐ๋ ์ค๊ฐ์ ํ๋ ์ง์ฐ๊ณ ๋๋ฉด ๊ทธ ๋ค์๊ป ๋ค ์์ผ๋ก ๋ก๊ฒจ์ผ ํ๋ค. ์ํ์๊ฐ ์ ๋ผ ์ค๋ ๊ฑธ๋ฆฐ๋ค. ํ์ง๋ง ๋ฆฌ์คํธ๋ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋ ํฌ์ธํฐ๋ง ๋ฐ๊ฟ์ฃผ๋ฉด ๋๋ค.)
- ๋จ์ : ์๋ชป๋ ํฌ์ธํฐ์ ์ํ Memory Leak ์ด ๋ฐ์ํ ์ ์๋ค.
2. ์๋ฐ๋ก ์ง ๋งํฌ๋ ๋ฆฌ์คํธ(c++๋ก ์ง๋ค๊ฐ ๊ฐ์๊ธฐ ๋น์ก์จ๊ฐ ๋ป์ด์ ๋ค ๋ ๋ผ๊ฐ์..--; ํ์์ฌ๋ผ์ ์์ ๋ก ๋ด๋ ค๋ ์๋ฐ ๋งํฌ๋ ๋ฆฌ์คํธ๋ฅผ ์ ๊ฒ ์ ¶
~cpp import java.io.*; class Node { private int ndata; public Node pNext=null; public Node(int ndata) { this.ndata=ndata; } public int getData() { return ndata; } } class MyLinkedList { private Node pHead; private Node pTail=null; private static int nNumber=0; public MyLinkedList() { pHead=new Node(0); } public void insertNode(int ndata,int nSequence) { Node pNew=new Node(ndata); if(nNumber==0) pHead.pNext=pNew; Node pTemp=new Node(0); pTemp=pHead; for(int i=0;i<nSequence;i++) pTemp=pTemp.pNext; pNew.pNext=pTemp.pNext; pTemp.pNext=pNew; nNumber++; } public boolean deleteNode(int nSequence) { if(nNumber<nSequence) { System.out.println("์ ์ฅ๋ ๋ฐ์ดํฐ์์ ์ด๊ณผํ๋ ์ธ๋ฑ์ค์ ๋๋ค!"); return false; } Node pTemp=new Node(0); Node pTemp2=new Node(0); pTemp=pHead; for(int i=0;i<nSequence-1;i++) pTemp=pTemp.pNext; pTemp2=pTemp.pNext; pTemp.pNext=pTemp2.pNext; nNumber--; return true; } public void showData() { Node pTemp=new Node(0); pTemp=pHead; int data; if(nNumber==0) System.out.println("์ ์ฅ๋ ๋ฐ์ดํฐ๊ฐ ์์ต๋๋ค!"); for(int i=0;i<nNumber;i++) { pTemp=pTemp.pNext; data=pTemp.getData(); System.out.println(data); } } public void showMenu() { System.out.println("1. Add"); System.out.println("2. Delete"); System.out.println("3. Show"); System.out.println("4. End"); System.out.print("Select the Menu : "); } public static void main(String args[]) { MyLinkedList ll=new MyLinkedList(); /// ์ด๋ถ๋ถ์ ๋ฉ๋ด๋ฅผ ๋ฃ๋ ํจ์ ํธ์ถ์ ํ๋ ๋ง์๋๋ก.. } }
- ๋ญ๊ฐ ๊ต์ฅํ ์ด์ํ๊ตฐ์..
; ์ ๊ฐ ๋ด๋..๊ต์ฅํ ์กฐ์กํ๊ณ ๊ต์ฅํ ํ์ ํ.. ๊ทธ๋ฐ ์ด์ํ ์ฝ๋ ๊ฐ์ต๋๋ค.
; ์๋ฐ๋ ์ฒจ์ด๋ผ์ ๊ทธ๋ฐ๊ฐ..;
- LinkedList๊ฐ ์ข
๋จ ๋ถ๋ถ์์๋ง ์ถ๊ฐ,์ญ์ ๊ฐ ๋๋๊ฒ ์๋ ์๋ฌด๋ฐ์๋ ๋์ผ ํ๋๊ตฐ์ฌ. ๊ทธ๋์ ๊ทธ๊ฑธ ์ด๋ป๊ฒ ์ ํด์ค๊น ๊ณ ๋ฏผํ๋ค๊ฐ ๋ฐ์ดํฐ์ ์์๋ก ํ๊ธฐ๋ก ํ์ต๋๋ค.
~cpp ์๋ ๋ค ์ ์ผ๋ฉด ์๋ฌด๋ ์๋ณผ๊ฑฐ ๊ฐ์์.. ์ธํฐํ์ด์ค์ ๊ฐ๋ต์ ์ธ ์๊ณ ๋ฆฌ์ฆ๋ง ์ ๊ฒ ์ต๋๋ค. ์ ๊ฐ ์๋ฐ๋ก ๋งํฌ๋ ๋ฆฌ์คํธ ์งค๋ ์ ์ผ ๊ณ ๋ฏผํ ์ ์ด ๋ ธ๋๋ฅผ ์ถ๊ฐํ ๋๋ง๋ค ์ ์ฒด ๋ ธ๋์ ํฌ๊ธฐ๊ฐ ๋ฐ๋๋ ์ ์ ๊ณ ๋ฏผ ๋ง์ด ํ์ต๋๋ค. ๊ทธ๋์ ํ๊ฒ์ด ๋ ธ๋๋ฅผ ์ถ๊ฐํ ๋๋ง๋ค ์ ์ฒด ๋ ธ๋๋ฅผ ๋ค์ ๋ง๋๋ ๊ฒ์ด์์ต๋๋ค. (์๋ฐ์ Vector ํด๋์ค์์ ์ด๋ ๊ฒ ํ๋ค๊ณ ์ผํ ๋ฃ์ด์...) ===> ๊ทธ ์์ ์ด ์๋์ ์์ต๋๋ค. boolean Add_ToSpecial(int coordi, int in) //ํน์ ํ ์์น์ ์๋ฃ๋ฅผ ์ ์ฅํ๋ ๋ฉ์๋ { if(coordi <0 || coordi >= m_Node.length) //์ขํ๋ 0๋ถํฐ ์์๋จ, ์ ๋ ฅ ์์น๊ฐ ํด๋น ๋ฒ์๋ฅผ ๋ฒ์ด๋ ๊ฒฝ์ฐ return false; Node tempNode[] = new Node[m_Node.length+1]; //m_Node์ ํ๋์ ์๋ฃ๋ฅผ ๋ ๋ฃ๊ธฐ ์ํด์ ์ด๋ณด๋ค //ํ๋์ ๊ณต๊ฐ์ด ๋ ๋ง์ ์์ ๋ฐฐ์ด์ ์์ฑํ๋ค. for(int i=0;i<tempNode.length-1 && i<coordi;i++) //tempNode์ m_Node๋ฅผ ์ฐ์ coordi๋ฒ์งธ(0๋ถํฐ ์์ํด์) ์ ์ ์๋ฆฌ tempNode[i] = m_Node[i]; //๊น์ง ๋ณต์ฌ ํ๋ค. Node tem = new Node(); //์์ ๋ ธ๋ ์์ฑ tem.item = in; tem.next = m_Node[coordi]; //๋ ๊ณณ์ ์๋ ์์๋ ์๋ฃ๋ฅผ ์ฐธ์กฐํ๋ค. tempNode[coordi] = tem; tempNode[coordi-1].next = tempNode[coordi]; //๋ ๊ณณ์ ๋ฐ๋ก ์์ ์๋ ์๋ฃ๊ฐ ์ฒจ๊ฐํ ์๋ฃ๋ฅผ ์ฐธ์กฐํ๊ฒ ํ๋ค. for(int j = coordi+1; j<tempNode.length-1;j++) tempNode[j] = m_Node[j-1]; m_Node = new Node[tempNode.length]; // m_Node์ ํฌ๊ธฐ๋ฅผ ๋๋ฆฐํ tempNode๋ฅผ ๋ฃ๋๋ค. for(int i=0;i<tempNode.length;i++) // m_Node ์ tempNode๋ฅผ ๋ณต์ฌํ๋ค. m_Node[i] = tempNode[i]; return true; } ////////////////////////// //๋ ธ๋ ํด๋์ค ๋ชจ์ต๊ณผ ์ธํฐํ์ด์ค class Node { //Node ํด๋์ค public int item; public Node next; } void Add_ToFront(int n) void Add_ToRear(int n) boolean Add_ToSpecial(int coordi, int in) boolean IsEmpty() boolean Delete_Front() boolean Delete_Rear() boolean Delete_Special(int coordi) void PrintAll()