U E D R , A S I H C RSS
ZeroWiki

Data Structure/List



[edit]

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 이 발생할 수 있다.

[edit]

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.0236 sec