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()