[자료구조] 2. 연결 리스트(Linked_List) -> deque

---

연결 리스트(Linked_List)

연결 리스트(Linked_List) deque

---

연결 리스트

특징, 장단점

특징
   1. 노드 기반 구조 : 데이터 , 포인터
   2. 비연속적 메모리 할당
   3. 동적 크기 조정

장점
   1. 동적인 메모리 관리
   2. 데이터 삽입. 삭제 편함

단점
   1. 메모리 오버헤드 : 각 노드가 데이터, 포인터를 저장, 메모리 많이 사용
   2. 순차 탐색 접근 : 배열과 달리 특정 요소에 접근하기 위해서는 리스트를 순차적으로 탐색해야함.

프로퍼티
   1. First() 첫번째 요소 값 가져오기
   2. Last() 마지막 값

프로퍼티 메서드
   1. AddFirst() 맨 앞 요소 추가
   2. AddLast() 맨 뒤 요소 추가
   3. AddBefore(x,y) x 요소 앞 y추가 (LinkedListNode, value)
   4. AddAfter(x,y) x 요소 뒤 y 추가 before,after은 LinkedListNode 를 사용하여야된다.
   5. Remove(x) x 요소 제거

LinkedList메서드 예시

LinkedList<int> lList = new LinkedList<int> (new[] {1,2,3,4});

int a = lList.First();  // a = 1
int b = lList.Last();   // b = 4 

lList.AddFirst(9);      // { 9, 1, 2, 3, 4 }
lList.RemoveFirst();    // { 1, 2, 3, 4 }
lList.AddLast(9);       // { 1, 2, 3, 4, 9 }
lList.RemoveLast();     // { 1, 2, 3, 4 }

LinkedListNode<int> pos = lList.Find(3);
LinkedListNode<int> firstpos = lList.First;
lList.AddBefore(pos,9);         // { 1, 2, 9, 3, 4 } 
lList.Remove(9);                // { 1, 2, 3, 4 } 
lList.AddAfter(firstpos, 9);    // { 1, 9, 2, 3, 4 }

게임 개발 활용

활용 상황
   1. 데이터가 자주 추가되거나 제거 상황
   2. 접근하는게 순차적일때
   3. 크기가 불확실할 때

활용 예시
   1. 동적 인벤토리 시스템
   2. npc 행동 관리(순차적)
   3. 레벨 내 동적 객체 관리(맵에서 적, 아이템 장애물 등 추가 제거)
   4. 멀티플레이어 게임에서 플레이어 관리(접속해제 빈번, 플레이어 관리 용이)
   5. 타이머 이벤트 관리(시간 순서 이벤트, 예전된 이벤트 실행, 제거에 편리)

GameObject(enemy) LinkedList 예시

using System.Collections.Generic;
using UnityEngine;

public class EnemyManager : MonoBehaviour
{
    private LinkedList<GameObject> enemies;

    void Start()
    {
        enemies = new LinkedList<GameObject>();

        // 적 캐릭터들을 연결 리스트에 추가
        foreach (var enemy in GameObject.FindGameObjectsWithTag("Enemy"))
        {
            enemies.AddLast(enemy);
        }
    }

    // 적 캐릭터 제거 함수
    public void RemoveEnemy(GameObject enemy)
    {
        enemies.Remove(enemy);
        Destroy(enemy);
    }
}

Linked List 로 Deque

[Deque 문제](https://www.acmicpc.net/problem/10866)

class Program
{
    static void Main()
    {
        {
            var sw = new StreamWriter(Console.OpenStandardOutput());

            int input =Convert.ToInt32(Console.ReadLine());
            //int[] inputArr = Array.ConvertAll(Console.ReadLine().Split(" "), Convert.ToInt32);
            
            LinkedList<int> deque = new LinkedList<int>();

            while (input-- > 0) 
            {
                string[] comarr = Console.ReadLine().Split(" ");
                string com = comarr[0];
                int num=0;
                if (comarr.Length ==2)
                {
                    num = Convert.ToInt32(comarr[1]);
                }

                commend(deque,com,num);
            }

            void commend(LinkedList<int> deque, string com, int num) 
            {
                if (com == "push_front")
                {
                    deque.AddFirst(num);
                }
                else if (com == "push_back")
                {
                    deque.AddLast(num);
                }
                else if (com == "pop_front")
                {
                    if (deque.Count>0)
                    {
                        sw.WriteLine(deque.First());
                        deque.RemoveFirst();
                    }
                    else
                    {
                        sw.WriteLine(-1);
                    }
                }
                else if (com == "pop_back")
                {
                    if (deque.Count > 0)
                    {
                        sw.WriteLine(deque.Last());
                        deque.RemoveLast();
                    }
                    else
                    {
                        sw.WriteLine(-1);
                    }
                }
                else if (com == "size")
                {
                    sw.WriteLine(deque.Count);
                }
                else if (com == "empty")
                {
                    if (deque.Count > 0)
                    {
                        sw.WriteLine(0);
                    }
                    else
                    {
                        sw.WriteLine(1);
                    }
                }
                else if (com == "front")
                {
                    if (deque.Count > 0)
                    {
                        sw.WriteLine(deque.First());
                    }
                    else
                    {
                        sw.WriteLine(-1);
                    }
                }
                else if (com == "back")
                {
                    if (deque.Count > 0)
                    {
                        sw.WriteLine(deque.Last());
                    }
                    else
                    {
                        sw.WriteLine(-1);
                    }
                }
            }

            sw.Flush(); sw.Close();
        }
    }
}

---

TOP

---