LinkedList
- 면접에서 List와 Linked List가 무엇인지 노드가 무엇인지 단골질문
- 직접 구현한 LinkedList를 확인하며 구조가 왜 이렇게 되었는지 이해하기
- 다음 노드의 주소를 참조하는 리스트
- 배열의 요소 하나를 노드 라고 한다
- Array와 List는 중간에 값이 추가되면 뒤에가 밀리면서 처리되기 때문에
삽입과 삭제가 매우 느림 - 다음 주소를 기억해야하므로 메모리를 더 잡아먹음
장점: 삽입과 삭제가 빠르다 ,시간복잡도 O(1)
이유: 중간에 하나가 삭제되거나 추가되도 그 이전의 노드가 추가된 노드를 가리키면 되기때문에
단점: 읽기, 탐색이 느리다. 인덱스로 접근 불가, 시간복잡도: O(N)
이유: 현재노드가 다음 노드의 주소를 가리키므로 노트를 확인하며 현재 찾는값이 맞는지 확인
코드1~3번을 자주 씀(c#에서 제공하는 링크드리스트)
코드1 (기본 사용법)
보통 C#에서 제공하는 링크드리스트를 쓴다고한다
class Program
{
static void Main(string[] args)
{
LinkedList<string> myLinkedList = new LinkedList<string>();
List<string> myList = new List<string>();
myLinkedList.AddLast("잘가!");
myLinkedList.AddFirst("쉬는 시간이야!");
myLinkedList.AddLast("잘가!2");
myLinkedList.AddFirst("쉬는 시간이야!2");
//myLinkedList.First.Previous.Previous.Previous();
foreach (var item in myLinkedList)
{
Console.WriteLine(item);
}
//코드결과
//쉬는 시간이야!2
//쉬는 시간이야!
//잘가!
//잘가!2코드2 LinkedListNode 이용
LinkedListNode를 이용해서 위치를 가져오고, 그 위치에 추가 및 삭제
class Program
{
static void Main(string[] args)
{
LinkedList<int> linkedList = new LinkedList<int>();
LinkedListNode<int> node; //중간에 데이터를 추가하기 위해서 사용한다.
linkedList.AddFirst(11);
// [11]
linkedList.AddLast(2);
// [11] [2]
node = linkedList.AddLast(23);
// [11] [2] [23]
// ▲node가 위치 기억
linkedList.AddLast(43);
// [11] [2] [23] [43]
// ▲node가 위치 기억
linkedList.AddAfter(node, 5);
//[11] [2] [23] [5] [43]
// ▲node가 위치 기억
linkedList.AddBefore(node, 12); //뭔가가 추가/ 삭제되도 계속 23의 노드를 가리킴
//[11] [2] [12] [23] [5] [43]
// ▲node가 위치 기억
linkedList.Remove(node);
//[11] [2] [12] [5] [43] //23위치 삭제
linkedList.Remove(2); //원하는값을 찾기까지 순회 O(n)
//[11] [12] [5] [43]
linkedList.RemoveFirst();
//[11] [12] [5] [43]
linkedList.RemoveLast();
//[12] [5]
if (linkedList.Contains(5)) //검색
{
foreach (int l in linkedList) //읽기
{
Console.WriteLine(l);
}
}
}코드3 LinkedList 조건문으로 Remove
삭제 포함해서 버프/디버프를 관리하는 코드
duration이 0이되면 삭제하고, UpdateBuffs로 1초씩 감소시킨다
public enum BuffType
{
Buff,DeBuff
}
public enum BuffName
{
Bleeding,Poisoning,StrengthUp,DefenseUp
}
public class Buff
{
//public string bufName;
public BuffType buffType;
public BuffName buffName;
public int duration;
public Buff(BuffType _buffType,BuffName _buffName, int _duration)
{
buffType = _buffType;
buffName = _buffName;
duration = _duration;
}
}
public class BuffManager
{
LinkedList<Buff> buffs = new LinkedList<Buff>();
public void AddBuff(BuffType _buffType,BuffName _buffName, int _duration)
{
Buff newBuff = new Buff(_buffType, _buffName, _duration);
buffs.AddLast(newBuff);
}
public void UpdateBuffs()
{
if (buffs.Count == 0) return;
LinkedListNode<Buff> current = buffs.First;
while(current != null)
{
LinkedListNode<Buff> next = current.Next;
current.Value.duration -= 1;
if(current.Value.duration<=0)
{
Console.WriteLine($"{current.Value.buffName} 해제");
buffs.Remove(current);
}
current = next;
}
}
public void ShowActiveBuffs()
{
foreach(var item in buffs)
{
if(item.buffType == BuffType.Buff) Console.ForegroundColor = ConsoleColor.Green;
else Console.ForegroundColor = ConsoleColor.Red;
Console.Write($"{item.buffType} ");
Console.ResetColor();
Console.WriteLine($"이름:{item.buffName}, 남은지속시간:{item.duration}");
}
}
}
class Program
{
static void Main(string[] args)
{
BuffManager buffManager = new BuffManager();
buffManager.AddBuff(BuffType.DeBuff,BuffName.Bleeding, 1);
buffManager.AddBuff(BuffType.DeBuff, BuffName.Poisoning, 2);
buffManager.AddBuff(BuffType.Buff, BuffName.StrengthUp, 4);
buffManager.AddBuff(BuffType.Buff, BuffName.DefenseUp, 5);
buffManager.ShowActiveBuffs();
Console.WriteLine("-------구분선-------");
buffManager.UpdateBuffs();
buffManager.UpdateBuffs();
buffManager.UpdateBuffs();
buffManager.UpdateBuffs();
buffManager.ShowActiveBuffs();
Console.WriteLine("----------------");
}
}실행결과
DeBuff 이름:Bleeding, 남은지속시간:1
DeBuff 이름:Poisoning, 남은지속시간:2
Buff 이름:StrengthUp, 남은지속시간:4
Buff 이름:DefenseUp, 남은지속시간:5
-------구분선-------
Bleeding 해제
Poisoning 해제
StrengthUp 해제
Buff 이름:DefenseUp, 남은지속시간:1
-------구분선-------
코드4 LinkedList 직접 구현
코드를 반복적으로 보면서 어떻게 노드를 구현했는지 확인 필요
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
public Node(T value)
{
Value = value;
Next = null; //다음 가리키는것은 아직없음
}
}
class LinkedList2<T>
{
public int Count { get; private set; }
public Node<T> Head { get; private set; }
public LinkedList2()
{
Head = null;
Count = 0;
}
//삭제 성공 여부 bool로 반환
//관리하고있는 리스트에 아무것도 없다면 false
public bool Remove(T value)
{
if (Head == null)
{
return false;
}
//1. 헤드가 삭제 대상인 경우
//if(Head.Value == value) //T는 ==이 안됨
if (Head.Value.Equals(value))
{
Head = Head.Next; //헤드 다음이 헤드가 됨
Count--;
return true;
}
//2. 중간 또는 끝 노드 탐색
Node<T> current = Head;
while (current.Next != null && !current.Next.Value.Equals(value))
{
current = current.Next;
}
if (current.Next == null)
{
return false;
}
//찾았으면 삭제처리
//currnet.Next는 지울곳, current.Next.Next로 지울곳의 연결을 끊고 다음것을 지정함
current.Next = current.Next.Next;
Count--;
return true;
}
//노드 찾기
public Node<T> Find(T value)
{
Node<T> current = Head; //항상 헤드시작
//해석해보기
while (current != null)
{
if (current.Value.Equals(value))
{
return current;
}
current = current.Next;
}
return null;
}
//Add Last
//리스트마지막에 Node추가
//Head가 null이면 처음 추가된 자가 Head
public void AddLast(T value)
{
Node<T> newNode = new Node<T>(value);
if (Head == null)
{
Head = newNode; //초기 head 설정
}
else
{
Node<T> current;
current = Head;
while (current.Next != null) //노드다음주소없는 마지막위치 찾음
{
current = current.Next;
}
current.Next = newNode;
//current = newNode; //이렇게 했을떄 왜 주소만 null이고 다 됬는지? 확인하기
//위 주석대로 하면 현재에 담겨서 현재 데이터 날라감(에러)
}
Count++;
}
}
class Program
{
static void Main(string[] args)
{
//### 사용자 정의 LinkedList 사용
LinkedList2<int> myLList = new LinkedList2<int>();
myLList.AddLast(1); //추가
myLList.AddLast(2); //추가
myLList.AddLast(15); //추가
//▼출력
Node<int> current;
current = myLList.Head;
while (current != null)
{
Console.WriteLine(current.Value);
current = current.Next;
}
Console.WriteLine("--구분선--");
//▼제거
current = myLList.Head;
myLList.Remove(2);
while (current != null)
{
Console.WriteLine(current.Value);
current = current.Next;
}
}
}
