U E D R , A S I H C RSS

Data Structure/List



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κ°€ 쒅단 λΆ€λΆ„μ—μ„œλ§Œ μΆ”κ°€,μ‚­μ œκ°€ λ˜λŠ”κ²Œ μ•„λ‹Œ μ•„λ¬΄λ°μ„œλ‚˜ λ˜μ•Ό ν•˜λ”κ΅°μ—¬. κ·Έλž˜μ„œ κ·Έκ±Έ μ–΄λ–»κ²Œ μ •ν•΄μ„κΉŒ κ³ λΌν•˜λ‹€κ°€ λ°μ΄ν„°μ˜ μˆœμ„œλ‘œ ν•˜κΈ°λ‘œ ν–ˆμŠ΅λ‹ˆλ‹€.

= μžλ°”λ‘œ μ§  λ§ν¬λ“œ 리슀트..2 (λˆ„κ°€ ν•œκ±ΈκΉŒ) μƒν˜‘μΈκ°€?=
~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() 



Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:05
Processing time 0.0207 sec