연결 리스트

연결리스트 이해를 위해 작성

---

생각해야할 것들
1. LinkedList
2. LinkedListNode

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

주의

• LinkedList는 기본적으로 인덱서를 지원하지 않는다. (임의의 접근 불가능)
• 데이터를 추가 할때 LinkedListNode에 저장은 가능하다.
• 만약 3번째 데이터에 접근하고 싶으면 Head를 기준으로 이동해서 찾을 수 밖에 없다.

---

LinkedList를 이해하기위해 방을 비유해서 코드

한 방을 기준으로 이전 방과 다음 방을 빠르게 접근할 수있다.
이전에 배운것을 보자면

class Room
{
	public Room Next;
    public Room Prev;
}

이런식으로 Room Next나Prev는 참조값(주소값)을 가지고있다.
(Room Next에 본체가 있는게 아니고 주소값을 가지고있어서 주소값으로 가니 방이 있다는 개념)

---

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;
    
    //O(1)
    public Room<T> AddLast(T data)
    {
   	 	Room<T> newRoom = new Room<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;
    }
    //O(1)
    public void Remove(Room<T> room) //몇번째 방(index개념)을 삭제하는게 아니라 방 자체를 삭제
    {
    	//RoomList에 속한 방의 예외처리가 필요하지만 지금은 생략
        
        //만약 첫번째 방을 삭제
        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--;
    }
}

Room이 있고 그 Room들을 연결시켜놓은 RoomList가 있다.
RoomList에서는 첫번째 방(Head) 와 마지막 방(Tail)의 정보를 계속 갱신 시켜줘야한다.

AddLast를 보면,
1.아직 첫번째 방이 없다면 지금 들어온 data가 저장되고 첫번째 방이 된다.
2.기존에 방이 있었다면 Tail이 있는거니 새로 추가된 방과 기존 Tail을 연결해준다.
3.마지막방은 이제 newRoom이고 Count를 저장해주고 return

Remove를 보면,
101 102 103 104 105가 존재할 때,
103을 삭제한다하면 102의 Next를 104로 연결시켜주고 104의 이전방을 102로 연결시켜주면 된다.

1. 만약 첫번째 방을 삭제한다면, 첫번째 방의 다음방을 Head로 지정한다.
   1.1 만약 첫번째 방만 있고 뒤에 아무것도 없다면 Head에는 null이 저장된다. 그래서 문제가 되지않는다.
2. 마지막 방을 삭제한다면, 기존의 마지막방의 이전방을 마지막 방으로 지정한다.
3. 일반적인 중간에 있는 값을 삭제한다면, 삭제하려는 방에 이전방의 다음방을 삭제하는방의 다음방으로 지정한다. 반대상황도 똑같이 지정한다.
   3.1 if(room.Prev !=null) 과 if(room.Next !=null) 코드 부분을 보면 이해가 쉽다.
4. 삭제완료를 했다면 Count--

---

visual studio에서 Ctrl + Shift + F 를 누르면 파일에 내용을 한번에 바꿀 수있다.
위에 코드에서 Room 을 MyLinkedListNode로 RoomList를 MyLinkedList 로 바꾸면
우리가 처음에 구현하고 싶었던 LinkedList가 된다.