선형 자료 기초
선형 구조는 자료를 순차적으로 나열한 상태
-배열
-연결 리스트
-스택 / 큐
비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태
-트리
-그래프
배열 vs 동적 배열 vs 연결리스트
현실생활에 항상 생각을 하자.
결국 자료구조와 알고리즘은 현실세계를 쉽게 하려고 하는 것이기 때문임.
호텔 방을 잡는다고 가정을 하자
배열 :
•
사용할 방 개수를 고정해서 계약하고 ( 절대 변경 불가)
•
연속된 방으로 배정 받아 사용
장점: 연속된 방
단점: 방을 추가/ 축소 불가
동적 배열:
•
사용할 방 개수를 유동적으로 계약
•
연속된 방으로 배정 받아 사용
문제점 : 이사 비용은 어떻게?? → 실제로 사용할 방보다 많이, 여유분을 두고 예약, 이사 횟수를 최소
장점: 유동적인 계약(방 추가 예약으로 이사 횟수 최소화)
단점: 중간 삽입/삭제의 어려움
연결리스트:
•
연속되지 않은 방을 사용
장점: 중간 추가/삭제 이점
단점: N번째 방을 바로 찾을 수가 없음( 임의 접근 Random Access불가)
동적 배열 구현 연습
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithm
{
class Board
{
public int[] _data = new int[25]; // 배열
public List<int> _data2 = new List<int>(); // 동적 배열
public LinkedList<int> _data3 = new LinkedList<int>(); // 연결 리스트
public void Initialize()
{
}
}
}
C#
복사
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithm
{
class MyList<T>
{
const int DEFAULT_SIZE = 1;
T[] _data = new T[DEFAULT_SIZE];
public int Count; //실제로 사용중인 데이터 개수
public int Capacity { get { return _data.Length; } } // 예약된 데이터 개수
//Add 함수 구현 알고리즘
// O(1) 예외 케이스임. 동적 배열에 아이템을 추가하는 것은 상수시간복잡도.
// 이사비용은 무시한다.
public void Add(T item)
{
// 1. 공간이 충분히 남아 있는 지 확인한다.
if (Count >= Capacity)
{
//공간을 다시 늘려서 확보한다.
T[] newArray = new T[Count * 2];
for(int i = 0; i < Count; i++)
newArray[i] = _data[i];
_data = newArray;
}
// 2. 공간에다가 데이터를 넣어준다.
_data[Count] = item;
Count++;
}
//O(1)
public T this[int index]
{
get { return _data[index]; }
set { _data[index] = value; }
}
//RemoveAt 함수 구현 알고리즘
//최악의 경우를 생각하면.. index = 0 일때..니까
//O(N)임.
public void RemoveAt(int index)
{
for (int i = index; i < Count - 1; i++)
_data[i] = _data[i + 1];
_data[Count - 1] = default(T);
Count--;
}
}
class Board
{
public int[] _data = new int[25]; // 배열
public MyList<int> _data2 = new MyList<int>(); // 동적 배열
public LinkedList<int> _data3 = new LinkedList<int>(); // 연결 리스트
public void Initialize()
{
_data2.Add(101);
_data2.Add(102);
_data2.Add(103);
_data2.Add(104);
_data2.Add(105);
int temp = _data2[2];
_data2.RemoveAt(2);
}
}
}
C#
복사
연결리스트 구현 연습
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithm
{
class Room<T>
{
public T Data;
public Room<T> Next;
public Room<T> Prev;
}
class RoomList<T>
{
public Room<T> Head = null; //첫번째
public Room<T> Tail = null; //마지막
public int Count = 0;
//AddLast
public Room<T> AddLast(T data)
{
Room<T> newRoom = new Room<T>();
newRoom.Data = data;
//만약에 아직 방이 아예 없었다면, 새로 추가한 첫 번째 방이 곧 Head
if (Head == null)
Head = newRoom;
// 기존의 [마지막 방] 과 [새로 추가되는 방]을 연결해준다.
if(Tail != null)
{
Tail.Next = newRoom;
newRoom.Prev = Tail;
}
// [새로 추가되는 방] 을 [마지막 방]으로 인정한다.
Tail = newRoom;
Count++;
return newRoom;
}
//Remove
public void Remove(Room<T> room)
{
//[기존의 첫 번째 방의 다음 방]을 [첫 번째 방으로] 인정한다.
if (Head == room)
Head = Head.Next;
//[기존의 마지막 방의 이전 방]을 [마지막 방으로] 인정한다.
if (Tail == room)
Tail = Tail.Prev;
if (room.Prev != null)
room.Prev.Next = room.Next;
if (room.Next != null)
room.Next.Prev = room.Prev;
Count--;
}
}
class Board
{
public int[] _data = new int[25]; // 배열
public LinkedList<int> _data3 = new LinkedList<int>(); // 연결 리스트
public void Initialize()
{
_data3.AddLast(101);
_data3.AddLast(102);
LinkedListNode<int> node = _data3.AddLast(103);
_data3.AddLast(104);
_data3.AddLast(105);
_data3.Remove(node);
}
}
}
C#
복사