3. 연결리스트 구현 연습
인프런 Rookiss 유니티 MMORPG 게임개발 시리즈 자료구조와 알고리즘을 듣고 리뷰한 내용.
연결리스트 구현해보기
c# LinkedList에 대해 MyLinkedList라는 임의 클래스를 생성하여 구현하려고 합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
namespace Exercise
{
internal class Program
{
public class MyLinkedListNode<T>
{
public T Data;
public MyLinkedListNode<T> Next;
public MyLinkedListNode<T> Prev;
}
public class MyLinkedListNodeList<T>
{
public MyLinkedListNode<T> Head = null; // 첫번째
public MyLinkedListNode<T> Tail = null; // 마지막
public int Count = 0; // 방의 갯수
// O(1)
public MyLinkedListNode<T> AddLast(T data)
{
MyLinkedListNode<T> newMyLinkedListNode = new MyLinkedListNode<T>();
newMyLinkedListNode.Data = data;
if (Head == null)
{
Head = newMyLinkedListNode;
}
if (Tail != null)
{
Tail.Next = newMyLinkedListNode;
newMyLinkedListNode.Prev = Tail;
}
// [새로 추가되는 방]을 [마지막 방]으로 인정한다.
Tail = newMyLinkedListNode;
Count++;
return newMyLinkedListNode;
}
// O(1)
public void Remove(MyLinkedListNode<T> MyLinkedListNode)
{
// [기존의 첫 번째 방의 다음 방]을 [첫 번쨰 방으로] 인정한다.
if (Head == MyLinkedListNode)
{
Head = Head.Next;
}
// [기존의 마지막 방의 이전 방]을 [마지막 방으로] 인정한다.
if (Tail == MyLinkedListNode)
{
Tail = Tail.Prev;
}
//
if (MyLinkedListNode.Prev != null)
{
MyLinkedListNode.Prev.Next = MyLinkedListNode.Next;
}
if (MyLinkedListNode.Next != null)
{
MyLinkedListNode.Next.Prev = MyLinkedListNode.Prev;
}
Count--;
}
}
static void Main(string[] args)
{
MyLinkedListNodeList<int> _data3 = new MyLinkedListNodeList<int>();
_data3.AddLast(101);
MyLinkedListNode<int> node = _data3.AddLast(102);
_data3.AddLast(103);
_data3.Remove(node);
}
}
}
변수
MyLinkedListNode
1
2
3
4
5
6
public class MyLinkedListNode<T>
{
public T Data;
public MyLinkedListNode<T> Next;
public MyLinkedListNode<T> Prev;
}
class MyLinkedListNode<T>T Data: 데이터MyLinkedListNode <T> NextMyLinkedListNode <T> Prev: 주소값을 들고 있음. 이것이 나 자신을 의미한다기보다 가르키고 있는 주소가 있다는 의미로 해석해야 한다. 해당Node라는 개념을 통해Node가 단순히 데이터를 담는 그릇일 뿐만 아니라 동시에 다음 노드를 가르키는 포인터(Next)와 이전 노드를 가르키는 포인터(Prev)를 가지고 있다. 따라서Data,Next,Prev변수가Node클래스 안에 구성되어 있다.
Head, Tail, Count
1
2
3
4
5
6
7
8
9
public class MyLinkedListNodeList<T>
{
public MyLinkedListNode<T> Head = null; // 첫번째
public MyLinkedListNode<T> Tail = null; // 마지막
public int Count = 0; // 방의 갯수
.
.
.
}
Head : 가장 첫번째(앞쪽에 있는) Node,
Tail : 가장 마지막(뒤쪽에 있는) Node,
Count : Node안에 들어있는 데이터의 갯수
처음에 이 선언 방식이 이해가 되지 않았다. 참조 타입(Node)이
Head와Tail를 기준으로 연결된다고 생각하면 된다. 배열을 생각하면 안된다!
함수
AddLast
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// O(1)
public MyLinkedListNode<T> AddLast(T data)
{
MyLinkedListNode<T> newMyLinkedListNode = new MyLinkedListNode<T>();
newMyLinkedListNode.Data = data;
if (Head == null)
{
Head = newMyLinkedListNode;
}
if (Tail != null)
{
Tail.Next = newMyLinkedListNode;
newMyLinkedListNode.Prev = Tail;
}
Tail = newMyLinkedListNode;
Count++;
return newMyLinkedListNode;
}
newMyLinkedListNode <- newNode로 간단히 표현해서 글을 작성했습니다.
- 데이터 추가 작업
newNode를 새로 하나 생성한다. (여기서 새로운 참조 값이 생긴다고 생각하자!.)newNode.Data안에 들어온data를 넣는다.- 첫 번째 실행 상황과 두번째 실행 상황.
- 첫 번째 실행 상황
Head,Tail에 연결된 데이터가newNode로 같다.
- 두 번째 실행 상황
Tail != null== true, 첫 번째 실행 때 할당됨.Tail != null조건식에 따라Tail.Next = newNode:Head.Next에도newNode가 할당된다.newNode.Prev = Tail:Tail은 이전newNode이다. 따라서현재 생성된newNode.Prev에이전에 생성된 newNode가 할당된 셈이다.
Tail = newNode:현재 생성된newNode.Prev에이전에 생성된 newNode가 할당.
- 첫 번째 실행 상황
Count++: 데이터가 들어오면 카운트 up.- 시간 복잡도 : O(1)
Remove
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// O(1)
public void Remove(MyLinkedListNode<T> MyLinkedListNode)
{
// [기존의 첫 번째 방의 다음 방]을 [첫 번쨰 방으로] 인정한다.
if (Head == MyLinkedListNode)
{
Head = Head.Next;
}
// [기존의 마지막 방의 이전 방]을 [마지막 방으로] 인정한다.
if (Tail == MyLinkedListNode)
{
Tail = Tail.Prev;
}
//
if (MyLinkedListNode.Prev != null)
{
MyLinkedListNode.Prev.Next = MyLinkedListNode.Next;
}
if (MyLinkedListNode.Next != null)
{
MyLinkedListNode.Next.Prev = MyLinkedListNode.Prev;
}
Count--;
}
MyLinkedListNode <- Node로 간단히 표현해서 글을 작성했습니다.
if (Head == Node) Head == Node:- Head와 Remove할 Node와 같으면,
- 기존의 첫 번째 Node의 다음 Node(Head.Next)를 첫 번째 Node(Head)에 할당한다.
if (Tail == Node) Tail == Node:- Tail와 Remove할 Node와 같으면,
- 기존의 마지막 Node의 이전 Node(Tail.Prev)를 마지막 Node(Tail)에 할당한다.
if (Node.Prev != null) Node.Prev.Next = Node.Next:- Remove할 Node의 Prev가 존재한다면, (Prev가 존재한다는 것은 Prev의 Next가 Node라는 이야기.)
- Prev.Next는 Node였다. 하지만 인제 Node의 Next로 할당한다.
if (Node.Next != null) Node.Next.Prev = Node.Prev:- Remove할 Node의 Next가 존재한다면, (Next가 존재한다는 것은 Next의 Prev가 Node라는 이야기.)
- Next.Prev는 Node였다 하지만 인제 Node의 Prev로 할당한다.
- 시간 복잡도 : O(1)
- 정리하자면, 양끝에 있는 Node를 제거하는 경우에는 각각 양끝 노드의 Next 혹은 Prev로 재할당한다. 중간 지점에 있는 Node의 경우,
Node.Prev.Next = Node.Next또는Node.Next.Prev = Node.Prev를 할당한다.
실행과정
사실 정리 겸 글을 작성했지만, 나중에 글만 읽으면 이해 못할 것 같다… 그래서 그림을 그리면서 정리해봤다… 여전히 조금 복잡한 감이 있지만, 코드 흐름을 파악하는 것에는 도움이 될 듯하다.
1
2
3
4
5
6
7
8
9
public MyLinkedListNodeList<int> _data3 = new MyLinkedListNodeList<int>();
public void Initialize()
{
_data3.AddLast(101);
LinkedListNode<int> node = _data3.AddLast(102);
_data3.AddLast(103);
_data3.Remove(node);
}
1. _data3.AddLast(101);
Head = newMyLinkedListNode;Tail = newMyLinkedListNode;
2. _data3.AddLast(102);
Tail.Next = newMyLinkedListNode;
newMyLinkedListNode.Prev = Tail;
Tail = newMyLinkedListNode;
3. _data3.AddLast(103);
Tail.Next = newMyLinkedListNode;
newMyLinkedListNode.Prev = Tail;
Tail = newMyLinkedNode;
4. _data3.Remove(node);
정리
연결리스트를 구현해보면서 여러 특징들을 느낄 수 있었다.
- 삽입과 삭제가 용이하다.
- 배열처럼 특정 사이즈를 정한 것이 아님으로 크기 자체도 유연하게 조정이 가능한 데이터 구조다.
- 배열이 아님으로 인덱스 접근은 어렵다.
- 구현 난이도가 있다.
위 내용은 이중 연결리스트를 구현한 내용이다. 단순 연결리스트, 원형 연결리스트도 나중에 한 번 구현해보면 좋을 것 같다.
This post is licensed under CC BY 4.0 by the author.