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