[자료 구조] 연결 리스트 구현 연습

구현할 부분

추가, 삭제

		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);
        }

구현

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    class MyLinkedListNode<T>
    {
        public T Data;
        public MyLinkedListNode<T> Next; //방을 가르키고 있는 주소
        public MyLinkedListNode<T> Prev; 
    }

    class MyLinkedList<T>
    {
        public MyLinkedListNode<T> Head = null; //첫번째
        public MyLinkedListNode<T> Tail = null; //마지막
        public int Count = 0;

        public MyLinkedListNode<T> AddLast(T data)
        {
            MyLinkedListNode<T> newRoom = new MyLinkedListNode<T>();
            newRoom.Data = data;

            //만약에 아직 방이 아예 없었다면, 새로 추가한 첫번째 방이 곧 Head이다.
            if (Head == null)
                Head = newRoom;

            //마지막 방이 이미 존재한다면, 
            //마지막 방과 새로 추가한 방을 연결해준 뒤 Tail을 갱신시켜준다.

            if (Tail != null)
            {
                Tail.Next = newRoom;
                newRoom.Prev = Tail;
            }

            // [새로 추가되는 방]을 [마지막 방]으로 인정한다.
            Tail = newRoom;
            Count++;
            return newRoom;
        }


        public void Remove(MyLinkedListNode<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
    {
        // c++과 c#에서 차이가 있음 Vector - List | List - LinkedList
        public int[] _data = new int[25]; //배열
      
        public MyLinkedList<int> _data3 = new MyLinkedList<int>();

        public void Initialize()
        {
            _data3.AddLast(101);
            _data3.AddLast(102);
            MyLinkedListNode<int> node = _data3.AddLast(103);
            _data3.AddLast(104);
            _data3.AddLast(105);

            _data3.Remove(node);
        }

    }
}

시간 복잡도 계산

AddLast(T data)

코드 수 고정

O(1)

public MyLinkedListNode<T> AddLast(T data)
        {
            MyLinkedListNode<T> newRoom = new MyLinkedListNode<T>();
            newRoom.Data = data;

            //만약에 아직 방이 아예 없었다면, 새로 추가한 첫번째 방이 곧 Head이다.
            if (Head == null)
                Head = newRoom;

            //마지막 방이 이미 존재한다면, 
            //마지막 방과 새로 추가한 방을 연결해준 뒤 Tail을 갱신시켜준다.

            if (Tail != null)
            {
                Tail.Next = newRoom;
                newRoom.Prev = Tail;
            }

            // [새로 추가되는 방]을 [마지막 방]으로 인정한다.
            Tail = newRoom;
            Count++;
            return newRoom;
        }


      
  

Remove(MyLinkedListNode room)

O(1)

  public void Remove(MyLinkedListNode<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--;
        }