24년 7월 10일 TIL

LinkedList

->선형자료구조란 직선. 직선직선자료구조 

일자로 쭉 뻗어진 자료구조 데이터를 랜덤한 접근이 아닌 순서대로 접근 할 경우에 배열보다 빠르다?

LinkedList는 데이터를 저장하는 자료구조 중 하나로, 각 요소가 노드 형태로 연결된 리스트다. 각 노드는 데이터와 함께 다음 노드에 대한 참조를 포함한다. C#에서는 System.Collections.Generic 네임스페이스 내에 LinkedList<T> 클래스가 제공됨.

 

 

 

나중에 정리.

LinkedList의 특성

• 연결된 노드: 각 노드는 데이터와 다음 노드에 대한 참조를 포함합니다.
• 양방향 링크드 리스트: C#의 LinkedList<T>는 양방향 링크드 리스트로 구현되어 있어, 각 노드가 이전 노드와 다음 노드에 대한 참조를 포함합니다.
• 동적 크기: 배열과 달리, LinkedList는 동적으로 크기가 조정됩니다.
• 빠른 삽입/삭제: 특정 위치에서의 삽입과 삭제가 빠릅니다. O(1) 시간 복잡도를 가집니다.

LinkedList의 사용 예

1. 특수 상황에서의 데이터 관리

• 데이터 삽입/삭제가 빈번할 때: 배열에서는 삽입/삭제 시 요소를 이동해야 하기 때문에 성능이 떨어질 수 있지만, LinkedList에서는 노드의 참조만 수정하면 되므로 더 효율적입니다.
• 큐와 스택 구현: LinkedList는 큐(Queue)와 스택(Stack)을 구현할 때 유용합니다.

2. Unity에서의 사용

Unity에서도 C#의 LinkedList<T>를 사용할 수 있으며, 주로 다음과 같은 상황에서 유용합니다:

• 게임 오브젝트 관리: 동적으로 생성되고 삭제되는 게임 오브젝트들을 관리할 때 유용합니다.
• 이벤트 시스템: 순차적으로 실행해야 하는 이벤트 체인을 관리할 때 사용할 수 있습니다.

LinkedList 사용 예제

 

using System; using System.Collections.Generic;

 

public class Program

{

     public static void Main()

     {

          LinkedList<int> numbers = new LinkedList<int>();

          // 요소 추가 numbers.AddLast(1); numbers.AddLast(2); numbers.AddLast(3);

          // 요소 삭제 numbers.Remove(2);

          // 요소 순회 foreach (var number in numbers)

          { Console.WriteLine(number); }

     }

}

 

LinkedList의 장점

• 빠른 삽입/삭제: 특정 위치에서의 삽입과 삭제가 빠릅니다.
• 동적 크기 조절: 배열과 달리 크기를 미리 지정할 필요가 없습니다.
• 효율적인 메모리 사용: 필요할 때마다 메모리를 할당하므로, 배열처럼 고정된 크기로 메모리를 낭비하지 않습니다.

LinkedList의 단점

• 느린 접근 속도: 특정 인덱스로 접근할 때 O(n) 시간이 걸립니다. 배열은 O(1) 시간 복잡도를 가지므로 훨씬 빠릅니다.
• 추가 메모리 사용: 각 노드가 데이터와 다음/이전 노드에 대한 참조를 포함하므로, 추가 메모리가 필요합니다.

LinkedList 사용 시 주의점

• 랜덤 접근이 빈번한 경우: 배열이나 List<T>가 더 적합합니다. LinkedList는 랜덤 접근이 느리기 때문에, 인덱스를 통해 자주 접근해야 하는 경우에는 성능이 떨어집니다.
• 메모리 효율이 중요한 경우: 추가적인 참조를 저장해야 하기 때문에, 메모리 사용이 중요한 애플리케이션에서는 부적합할 수 있습니다.

결론

LinkedList는 데이터의 빈번한 삽입 및 삭제가 필요한 경우에 매우 유용한 자료구조입니다. 그러나 특정 인덱스로 자주 접근해야 하거나 메모리 사용이 중요한 경우에는 배열이나 List<T> 같은 다른 자료구조가 더 적합할 수 있습니다. Unity에서 게임 오브젝트를 동적으로 관리하거나 이벤트 체인을 구현할 때도 유용하게 사용할 수 있습니다.

 

 

클래스 및 주요 멤버 변수

• Node: 데이터와 다음 노드를 저장하는 내부 클래스.
  • Data: 노드가 저장하는 데이터.
  • Next: 다음 노드를 가리키는 포인터.
• My_LinkedList<T>: LinkedList를 구현하는 클래스.
  • head: 리스트의 첫 번째 노드를 가리키는 포인터.
  • count: 리스트의 노드 개수를 저장하는 정수.

함수

1. IsEmpty: 리스트가 비어있는지 확인하는 함수.
   • 입력: 없음.
   • 출력: 리스트가 비어있으면 true, 아니면 false.
2. AddFirst: 리스트의 맨 앞에 노드를 추가하는 함수.
   • 입력: 추가할 데이터 item.
   • 출력: 없음.
3. Insert: 리스트의 n번째 노드 뒤에 새로운 노드를 삽입하는 함수.
   • 입력: 삽입할 위치 n (0-based index)와 추가할 데이터 item.
   • 출력: 없음.
   • 동작:
     • n이 0이면 AddFirst를 호출하여 맨 앞에 노드를 추가합니다.
     • n이 0보다 큰 경우:
       • 현재 노드를 head로 설정하고, 현재 노드가 null일 때까지 또는 n-1 번 반복합니다.
       • 각 반복에서 현재 노드를 다음 노드로 업데이트합니다.
       • 반복 후의 현재 노드가 null이면 예외를 발생시킵니다.
       • 새로운 노드를 생성하고, 그 노드의 Data 필드에 item을 저장합니다.
       • 새로운 노드의 Next 필드를 현재 노드의 Next로 설정합니다.
       • 현재 노드의 Next를 새로운 노드로 설정합니다.
       • count를 1 증가시킵니다.
4. RemoveFirst: 리스트의 첫 번째 노드를 제거하고 그 데이터를 반환하는 함수.
   • 입력: 없음.
   • 출력: 제거된 노드의 데이터.
5. Remove: 리스트의 n번째 노드를 제거하고 그 데이터를 반환하는 함수.
   • 입력: 제거할 노드의 위치 n (0-based index).
   • 출력: 제거된 노드의 데이터.
   • 동작:
     • n이 0이면 RemoveFirst를 호출하여 첫 번째 노드를 제거합니다.
     • n이 0보다 큰 경우:
       • 현재 노드를 head로 설정하고, 현재 노드가 null일 때까지 또는 n-1 번 반복합니다.
       • 각 반복에서 현재 노드를 다음 노드로 업데이트합니다.
       • 반복 후의 현재 노드가 null이면 예외를 발생시킵니다.
       • 제거할 노드를 현재 노드의 Next로 설정합니다.
       • 현재 노드의 Next를 제거할 노드의 Next로 설정합니다.
       • 제거할 노드의 데이터를 임시 변수에 저장합니다.
       • count를 1 감소시킵니다.
       • 임시 변수에 저장된 데이터를 반환합니다.
6. Count: 리스트의 노드 개수를 반환하는 함수.
   • 입력: 없음.
   • 출력: 리스트의 노드 개수.
7. PrintAllNodes: 리스트의 모든 노드를 출력하는 함수.
   • 입력: 없음.
   • 출력: 없음.

 

4o