[TIL] 자료구조

자료 구조

1. Linked List
2. Stack
3. Queue
4. Tree

 

 

링크드 리스트(Linked List)

값과 다음 값을 가리키는 연결로 데이터를 컨테이닝 하는 자료구조

링크드 리스트는 노드로 이루어져 있으며 노드는 값과 다음 값의 위치를 담고있는 링크드 포인트로 이루어져있다

 

다음 노드로의 연결만 구현되있는 단순 연결 링크드 리스크가 있고 

앞 뒤 노드 모두와  연결 되있는 링크드 리스트가 있다.(이중 연결 리스트)

 

C#에서 지원하는 링크드 리스트는 이중 연결 리스트이다.

 

선언

LinkedList<float> IList = new LinkedList<float();

private void UseLinkedList()
{
	IList.AddLast(0); //맨 뒤에 값 넣기
	IList.AddFirst(-1);//맨 앞에 값 넣기
	LinkedListNode<float> targetNode= IList.First;
	LinkedListNode targetNode= IList.Find(1);//없는 값 넣으면 null 뜸
	IList.AddAfter(targetMode,0.5f);
}

 

• .AddLast() 맨 뒤에 값을 넣는다.
• .AddFirst() 맨 앞에 값을넣는다,

기본적으로 링크 리스트는 인덱스 번호로 접근할 수 없다. 

따라서 특정값을 중간에 삽입하려면 LinkedListNode를 사용해야한다.

• LinkedListNode tragetNode= IList.Find(찾는 값)  리스트에 있는 값을 넣어야한다. 아닐시 null값이 뜬다.
• IList.AddAfter(tragetNode. 넣고싶은 값) LinkedListNode 의 값 뒤에 원하는 값을 넣는다.

foreach(var f  in IList) //출력 함수
{
	console.WriteLine(f);
}

 

 

링크드 리스트와 리스트의 차이

큰 차이점은 리스트는 바로바로 접근이 가능하고 인덱스 번호로 접근할 수 있다. ( 검색이 빠르다.)

반면 링크드 리스트는 검색 속도는 느리지만 데이터의 추가 삭제 속도는 빠르다.

하지만 메모리 효율성이 낮아 대규모 데이터에는 부적합 하다(보통 리스트나 배열이 사용)

 

일반적으로 링크  링크드 리스트를 쓰는 경우는 거의 없지만. 가끔 코딩 테스트에서 시간이 걸리는 경우에 사용한다고한다.

 

 

스택 (stack) 후입 선출

가장 늦게 들어온 값이 가장 먼저 나간다.

Stack<float> fStack= new Stack<float>();

public void UseStack()
{
    fStack.Push(1);
    fStack.Push(2);
    fStack.Push(3);
    fStack.Pop();

    fStack.Peek(); //제일 위에 있는 값 == 꼭대기 값
    fstack.Last(); // 가장 아래에 있는 값 ==바닥 값
}

• .Push(값) 스택에 값을 넣는다.
• .Pop() 스택에 가장 위에있는 값을 없앤다.
• .Peek() 제일 위에 있는 값을 불러온다.
• .Last() 가장 바닥에 있는 값을 불러온다,

 

스택을 활용하는 기능 중 대표적인 것이 Ctrl +z (뒤로가기)

게임에서는 UI팝업창 등이 사용 예시이다.

 

 

큐(Queue) 선입 선출

가장 먼저 들어온 값이 먼저 나간다.

private Queue<float> numQ = new Queue<float>();

 

public void UesQueue()
{
    numQ.Enqueue(0)
    numQ.Dequeue();
    numQ.First(); //맨 앞의 값
    numQ.Last();// 맨 뒤의 값
}

 

• .Enqueue(값) 큐에 값을 넣는다
• .Dequeue 가장 먼저 들어온 값을 없앤다.
• .First() 맨 앞의 값을 반환한다.
• .Last() 맨 뒤의 값을 반환한다.

우선 순위 큐(PriorityQueue)

우선 순위 큐는 가장 먼저 들어온 값이 먼저 나가지 않고 우선순위대로 정렬해서 먼저나간다

우선순위에 따라서 출력되는 순서가 다르다.

public class PriorityData
{
    public int priority;
    public string name;
    
    public ProrityData(int p, string n)
    {
      priority = p;
      name= n;
    } 
}

UsePriorityQueue()
{
    Queue<PriorityData> foodq = new Queue<PriorityData>();

    PriorityData food1 = new Priorituata( 2, "민초");
    foodq.Enqueue(food1);
    PriorityData food2 = new Priorituata( 1, "파인애플 피자");
    foodq.Enqueue(food2);
    PriorityData food3 = new Priorituata( 0, "솔의 눈");
    foodq.Enqueue(food3);
    Queue<PriorityData> orderFoodQ = new Queue<ProrityData>(foodq.OrderBy(x=> x.priority));

    for(int i=0; i <3 ; i++)
    {
        Consoel.WriteLine(foodq.Dequeue().name);//넣은 순서대로 넣음
        Consoel.WriteLine( orderFoodQ .Dequeue().name);// 우선순위 대로나옴
    }
}

 

 

이렇게 직접 만들어도 되지만 C#은 우선순위 큐를 제공한다.

PriorityQueue <string,int> pq= new PriorityQueue<string, int>();//값, 우선순위

pq.Enqueue("Bronze",2);
pq.Enqueue("Silver",1);
pq.Enqueue("Gold",0);

 

 

트리(Tree)

비 선형 자료이다.

데이터 연결이 일렬이 아니다.

public class TreeNode
{
    public int value;
    public TreeNode parent;
    public TreeNode Left;
    public TreeNoe Right;

    public( TreeNode(int v)
    {
    	value = v;
    }
}

public class BSTree()
{
    public TreeNode Root;
    public BSTree()
    
    public BSTree(int v)
    {
    	Root = new TreeNode(v);
    }
    
    public void Add(int num)
    {
    	if(Root == null)
    	{
            Root = new TreeNode(num);
            return ;
		}
	}
	TreeNode compare =Root;
    
    while(true)
    {
        if(compare.calue <= num)
        { 
        	if(compare.Right ==null)
        	{
                TreeNode right = new TreeNode(num);
                compare.Right = right;
                right.Parent = compare;
                break;
    		} 
            else
            {
              compare = compare.Right;
            }

        else 
        {
            if(compare.Left == null)
            {
                TreeNode left = new TreeNode(num); 
                compare.Left= left;
                left.Parent =compare;
                break;
            }
            else
            compare= compare.left;
        }
}

class LearnTree
{
    public voi UseBstree()
    {
        BSTree bst = new BsTree();
        int[] nums = {8, 13, 3, 1, 10, 6, 14, 7,4,};
        
        for( int i=0; i< nums.Length; i++)
        {
        	bst.add(num[i];
        }
    }
}

트리 구조는 너무 어렵..

트리는 알아두면 적 AI를 설정할때 유용하다고 한다.