List
List가 무엇인가?
배열 기반의 자료구조 -> 배열의 특징들 사용 가능 메모리에 연속적으로 데이터가 저장되며 인덱스 기능 구현이 가능하기에 탐색에 유리하다.
배열의 경우 생성과 동시에 크기가 소멸할 때 까지 유지가 되므로 런타임 도중 가변하는 자료에 대한 대처가 힘들기 때문에 리스트를 고안하였다.
하지만 배열과의 차이점은 array.Length와 달리
List.Capacity / List.Count로 두개가 있다는 것인데, 배열은 항상 요소 모두를 사용하기에 Length를 사용하여 배열의 크기를 통해동작을하지만 List의 경우 담을수있는 허용용량(Capacity)과 담겨져 있는 데이터의 개수를(Count)로 구분지어 사용을 한다.
cf) 배열이란?
배열은 메모리에 연속적으로 동일한 자료형의 데이터를 저장하는 방식으로. 생성시에 크기가 정해져서 삭제까지 유지되는 특징이 있다.
메모리에 연속적으로 데이터를 저장하므로, 인덱스 값의 사용이 가능하고, 첫번째 요소의 데이터에서 자료형의크기x인덱스 값을 통해 특정 인덱스로의 빠른 접근이 가능하다.
List사용처?
런타임도중 개수가 지속적으로 바뀌는 값.
Big-O
접근 : O(1)
탐색 : O(n)
삽입 : O(n)
삭제 : O(n)
List구현
// 초기화
internal Class List<T>{
private const int DefaultCapacity = 4;
private T[] items;
private int size;
//생성자
public List(){
items = new T[DefaultCapacity];
size = 0;
}
//프로퍼티
public int Capacity{get {return items.Length;}}
public int Count{get{return size;}}
public T this[int index]{
get{
if(index <0 || index >= size)
throw new IndexOutOfRangeException;
return items[index];
}
set{
if(index <0 || index >= size)
throw new IndexOutOfRangeException;
items[index] = value;
}
}
public void Add(T item){
if(size >= items.Length){
Grow();
}if
items[size++] = item;
}
public void Clear(){
items = new T[DefaultCapcity];
size = 0;
}
public T? Find(Predicate<T> match){
if(match == null) throw new ArgumentNullException();
for(int i = 0; i < size ; i++){
if(match(items[i]))
return itmes[i];
}
return default(T);
}
public int FindIndex(int startIndex, int count, Predicate<T> match){
if(startIndex > size)
throw new ArgumentOutOfRangeException();
if(count < 0 || startIndex > size -count)
throw new ArgumentOutOfRangeException();
if(match == null)
throw new ArgumentNullException();
int endIndex = startIndex +count;
for(int i = startIndex ; i<endIndex; i++){
if(match(items[i])) return i;
}
return -1;
}
//특정 위치 삭제
public void RemoveAt(int index){
if(index < 0 || index > size)
throw new IndexOutOfRangeException();
size--;
Array.Copy(items, index+1, items, index, size - index);
}
//크기 키우기
private void Grow(){
int newCapacity = array.Length*2;
T[] newItems = T[newCapacity];
Array.Copy(item, 0, newItems, 0, size);
items = newItems;
}LinkedList
LinkedList가 무엇인가?
노드 기반의 자료 구조
노드에는 해당 본인이 포함된 list의 정보와 이전/이후 노드의 주소 / 데이터 값이 존재하며 노드들은 메모리에 연속적으로 배치되지 않고 이전/다음노드의 위치 확인을 위해 참조가 가능하다.
인덱스 사용이 불가능하며 탐색에 head부터 일일이 찾아가야 하는 단점이 있다.
그러나 삽입 삭제에 있어서는 앞뒤의 노드의 참조값만 바꿔주면 되기 때문에 매우 간편하다.
LinkedList사용처?
데이터의 삽입과 삭제에 강점을 보이므로 빈번한 데이터의 변경이 일어나는 경우 유용함.
Big-O
접근 : O(n)
탐색 : O(n)
삽입 : O(1)
삭제 : O(1)
LinkedList 구현(간략히)
//node 구현
public class LinkedListNode<T>{
//노드는 본인이 속한 LinkedList와 이번/이후노드/그리고 값을 가짐.
internal LinkedList<T> list;
internal LinkedListNode<T> prev;
internal LinkedListNode<T> next;
private T item;
//오버로딩해서 쓰지만 지금은 일단 간단히 두개만
public LinkedListNode(T value){
this.list = list;
this.prev = null;
this.next = null;
this.item = value;
}
public LinkedListNode(LinkedList<T> list, LinkedListNode<T> prev, LinkedListNode<T> next, T value){
this.list = list;
this.prev = prev;
this.next = next;
this.item = value;
}
//프로퍼티
public LinkedList<T> List { get { return list; } }
public LinkedListNode<T> Prev { get { return prev; }}
public LinkedListNode<T> Next { get { return next; }}
public T item{get {return item;} set {item = value;}}
}
//LinkedList구현
public class LinkedList<T>{
// LinkedList의 경우 head/tail의 값과 총 개수 count만 가지고있음.
private LinkedListNode<T> head;
private LinkedListNode<T> tail;
private int count;
//생성자
public LinkedList(){
this.head = null;
this.tail = null;
count = 0;
}
//프로퍼티
public LinkedListNode<T> First{get {return head;}}
public LinkedListNode<T> Last{get {return tail;}}
public int Count{get{return count;}}
//삽입
public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value){
ValidateNode(node);
LinkedListNode<T> newNode = LinkedListNode<T>(this, value);
InsertNodeBefore(node, newNode);
if(node == head)
head = newNode;
return newNode;
}
//탐색
public LinkedListNode<T> Find(T value){
LinkedListNode<T>? node = head;
EqualityComparer<T> c = EqualityComparer<T>.Default;
if (value != null){
while (node != null){
if (c.Equals(node.Item, value))
return node;
else
node = node.next;
}
}
else{
while (node != null){
if (node.Item == null)
return node;
else
node = node.next;
}
}
return null;
}
//삭제
public bool Remove(T value){
LinkedListNode<T>? node = Find(value);
if (node != null)
{
Remove(node);
return true;
}
else
{
return false;
}
}
//유효노드검사
private void ValidateNode(LinkedListNode<T> node){ if (node == null)
throw new ArgumentNullException();
if (node.list != this)
throw new InvalidOperationException();
}
//특정 노드 앞에 삽입
priate void InsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode){
newNode.next = node;
newNode.prev = node.prev;
if(newNode.prev != null)
newNode.prev.next = newNode;
node.prev = newNode;
count ++;
}
}cf) Delegate의 종류인 Action / Func / Predicate
Action -> return 값이 없음 Action<매개변수>로 사용가능
Func -> return 값이 존재함 Action<매개변수, return값 자료형>로 사용
Predicate -> return값이 bool자료형 Predicate<매개변수>로 사용가능
cf2) Delegate?
메서드를 다른 메서드로 전달할 수 있도록 만듦.
보통 Method에 파라미터로 int값이나 bool값을 넘겨주는 것과 같이 파라미터로 메서드를 넘겨주는 것이 delegate이다.
delegate에서 중요한것은 입력파라미터들과 리턴타입이다.
어떤 메서드든 델리케이트의 원형과 일치한다면(반환값/리턴) 그 메서드는 해당 델리케이트에서 사용될 수 있다.
<사용예제>
static void Main(string[] args)
{
new Program().Test();
}
// 델리게이트 정의
delegate int MyDelegate(string s);
void Test()
{
//델리게이트 객체 생성
MyDelegate m = new MyDelegate(StringToInt);
//델리게이트 객체를 메서드로 전달
Run(m);
}
// 델리게이트 대상이 되는 어떤 메서드
int StringToInt(string s)
{
return int.Parse(s);
}
// 델리게이트를 전달 받는 메서드
void Run(MyDelegate m)
{
// 델리게이트로부터 메서드 실행
int i = m("123");
Console.WriteLine(i);
}cf3) 생성자?
클래스에서 객체를 생성할 때 객체를 초기화 가능.
여러개의 생성자를 둘 수 있지만 이 중 하나만 실행되며 특정 파라미터 값을 넣어줄 경우 원하는 파라미터를 가진 클래스를 인스턴스가 가능
특징
- 생성자의 목적은 객체가 생성될 때 필요한 초기 작업을 위함이다
- 생성자 함수는 오직 한번만 실행된다. -> 객체마다 단한번
- 생성자 함수의 이름은 클래스 이름과 동일하게 작성되어야 한다.
- 생성자 함수의 원형에 리턴 타입을 선언하지 않는다.
- 생성자는 중복해서 오버로딩과 비슷하게 선언이 가능.
Reference)
https://github.com/jungtaek6681/CSharp-Algorithm
https://www.csharpstudy.com/CSharp/CSharp-delegate-concept.aspx
https://jyoel.tistory.com/7
