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










