0329 자료구조 (배열과 링크드 리스트)

데이터의 구조를 만들어 데이터를 저장하고 관리하는 것

잘 설계된 자료구조는 실행시간을 최소화하고 소요 공간을 최소한으로 사용하면서 연산을 수행할 수 있도록 한다.

 

추상적 자료형 : 알고지름이 문제를 해결하는데 필요한 자료의 형태와 그 자료를 사용한 연산들을 수학적으로 정의한 모델

무엇이 구현되어야 하는 지를 정의한 것, 논리적 형태로 정의한다.

 

자료구조의 종류:

1. 단순 구조 - 기본적인 데이터 타입으로 정수/실수/문자/불

2. 선형 구조 - 배열, 연결 리스트, 스택, 큐 같은 자료구조

3. 비선형 구조 - 1:다 , 다 대 다와 같은 구조. 트리, 그래프 등

4. 파일 구조

---

Array

순차적/일렬로 저장하는 자료구조

고정 크기를 가지며, 배열은 고정적이다.

 

Jagged Array 가변 배열

[][] 배열의 배열처럼 사각 괄호를 겹쳐서 차원을 표현한다.

int[][] A=new int[3][];

public class App
    {
        public App()
        {
            //가변 배열 선언
            int[][] arr = new int[3][];
            arr[0] = new int[2];
            arr[1] = new int[6] { 1, 2, 3, 4, 5, 6 };
            arr[2] = new int[3] { 4, 5, 6 };

            Console.WriteLine(arr);

            for (int i = 0; i < arr.Length; i++) 
            {   for (int j = 0; j < arr[i].Length; j++) 
                {
                    int[] arr2 = arr[i];
                    Console.Write(arr2[j] + "");
                }
            }Console.WriteLine();
        }   
    }

 

 

Dynamic Array 동적 배열

배열의 최대 크기를 미리 알 수 없는 경우 크기를 늘린다.

public class DynamicArray
    {
        private int capacity;
        private const int GRWOTH_FACTOR = 2;
        private int[] arr;
        private int count; //배열의 꽉참을 알기 위해

        public DynamicArray(int capacity=2) 
        {
            this.capacity = capacity;
            this.arr = new int[this.capacity];
        }
        public void Add(int element) 
        {
            //꽉참
            if (this.count >= capacity) 
            {
                //확장
                int newSize = this.capacity * GRWOTH_FACTOR;
                int[] temp = new int[newSize];
                for (int i = 0; i < this.arr.Length; i++)
                {
                    temp[i] = arr[i];
                }
                this.arr = temp;
            }
            this.arr[count] = element;
            count++;
        }
        public int Get(int index) 
        {
            return -1;
        }
        public void Print() 
        {
            for (int i = 0; i < arr.Length; i++) 
            {
                Console.WriteLine("{0}", i);
            }
        }
    }

growth_factor는 대부분 2, 1.5배 증가로 한다.

 

 

Circular Array 원형 배열

배열의 크기가 n일때 배열의 마지막 요소(n-1)에 도착하면, 다음 배열 요소는 첫번째 요소로 순환하는 배열

mod 연산자를 이용해 마지막 인덱스에서 0인덱스로 돌아오게 한다.

int startIndex = 2;
                for (int i = 0; i < arr.Length; i++)
                {
                    int index = (startIndex + i) % arr.Length;
                    Console.WriteLine(index);
                }for (int i =0; i<arr.Length; i++){int index = (startIndex +i) % arr.Length;Console.WriteLine(index[i]);}

 

 

Linked List 연결 리스트

galid1.tistory.com/92

각 노드들이 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식

단일 연결 리스트(Singly Linked List) 노드를 표현하는 노드 클래스와 링크드 리스트 클래스 두 개가 필요하다.

리스트의 첫 노드를 가리키는 헤드(Head)필드를 가지게 되는데, 이 Head를 사용하여 전체 리스트를 순차적으로 엑세스한다.

 

Add();

리스트가 비어있으면 head 에 새 노드를 할당하고, 비어 있지 않으면 마지막 노드를 찾아 이동한 수 마지막 노드 다음에 새 노드를 추가한다.

public class Node
    {
        public int data;
        public Node next;
        public Node(int data) 
        {
            this.data = data;
        }
    }
    public class SingleLinkedList
    {
        private Node head; //헤드부터 순차적 접근하기 위함
        public SingleLinkedList()  
        { }
        
        //노드 추가
        public void Add(Node node) 
        {
            if (this.head == null)
            {
                this.head = node;
            }
            else 
            {
                //head부터 next가 null 일 것 찾기
                //비교 대상을 임시저장
                Node current = this.head;
                while (current != null && current.next != null) 
                {
                    //next가 있음
                    current = current.next;
                }
                //새로운 노드 연결
                current.next = node;
            }
        }
        //노드 수 세기
        public int Count() 
        {
            int count = 0;
            Node current = this.head;
            while (current != null) 
            {
                count++;
                current = current.next;
            }
            return count;
        }
    }

public class App
    {   
        public App()
        {
            SingleLinkedList list = new SingleLinkedList();
            list.Add(new Node(1));
            list.Add(new Node(2));
            Console.WriteLine(list.Count());
        }
    }

 

AddAfter();

새 노드의 next에 현재 노드의 next를 먼저 할당하고, 현대 노드의 next에 새 노드를 할당한다.

public void AddAfter(Node current,Node newNode) 
        {
            if (this.head == null || current == null || newNode == null) 
            {
                throw new InvalidOperationException();
            }
            newNode.next = current.next;
            current.next = newNode;
        }

 

Remove();

public void Remove(Node removeNode) 
        {
            if (this.head == null||removeNode==null) 
            {
                throw new InvalidOperationException();
            }
            //만일 지우려는 것이 head라면
            if (this.head == removeNode)
            {
                this.head = this.head.next;
                removeNode = null;
            }
            else 
            {
                Node current = this.head;
                while (current != null && current.next != removeNode)
                {
                    current = current.next;
                }
                current.next = removeNode.next;
            }
        }