Linked List, 연결리스트

Linked List를 간략하게 설명한다면?

a list of nodes that are linked together.

• singly linked list
• doubly linked list

---

Linear data structures : 선형 데이터 구조

• sequence(순서와 규칙)가 있다
• hopscotch처럼 끝에 다다르기 위해서는 순차적으로 모든 노드를 지나쳐야 한다.

hopscotch

Linear	Non-Linear
Array, linked list	hashes, trees, graphs

---

Memory Management

같은 선형 데이터인 Array와 linked List의 차이가 뭘까?

 

7개의 문자를 저장하는 Array가 만들어지면, 연속된 7byte짜리의 메모리 칸을 마련해두어야 한다.

하지만, linked list는 연속된 single block이 아니라 scattered 하게 메모리를 할당할 수 있음

 

Array	Linked List
static data structure	dynamic data structure
all of its resourceds to be allocated when the structure is created	size and shape can change  자유롭게 shrink, expand

---

Node: 연결 리스트의 노드

• 첫 노드: starting point
• 마지막 노드: Null을 가리키고 있다면 마지막 노드

노드가 알고 있는 것

• Data: 노드가 가진 값
• Neighbor: 노드가 가리키는 곳

sigle node는 연결리스트 총 길이를 모른다. 그리고 어디서 시작하고 어디서 끝나는지도 모른다.

 

 

---

 

 

https://machineboy0.tistory.com/160

Ordered Data Structures # WEEK1 : Arrays VS Linked Memory 개념

 

https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d

What’s a Linked List, Anyway? [Part 1]

---

Doubly Linked List 구현해보기

1) Deque<T>

 

Deque는 양방향 큐, 즉 앞 뒤 방향에서 요소를 추가, 삭제할 수 있는 자료 구조를 의미한다.

Deque의 요소가 제너릭 타입 <T>, 즉 어떠한 형태도 들어갈 수 있음을 의미한다.

 

2) Node 생성

 

이중연결리스트를 만들것이므로, 단일 노드가 가지고 있어야 하는 값은 다음과 같다.

• value : 해당 노드가 지닌 값
• prev : 이전 노드
• next : 다음 노드

class Node
{
    public T Value;
    public Node prev;
    public Node next;
}

 

3) Head와 Tail Node 생성

Node head = null;
Node tail = null;

현재 비어 있는 상태

4) Push : 뒤에서 노드 추가

public void Push(T value)
{
	Node node = new Node();
    node.Value = value;
    
    if(tail == null){
    	head = node;
        tail = node;
    }
    else{
    	tail.next = node;
        node.prev = tail;
        tail = node;
    }
}

 

5) Pop : 뒤에서 노드 제거 후, 그 값 추출

public T Pop()
{
	if(tail == null) return default(T);
    
    T value = tail.Value;
    
    if(head == tail)
    {
    	head = null;
        tail = null;
    }
    else
    {
    	tail = tail.prev;
        tail.next = null;
    }
    
    return value;
}

 

6) Unshift : 앞 추가

public void Unshift(T value)
{
	Node node = new Node();
    node.Value = value;
    
    if(head == null)
    {
    	head = node;
        tail = node;
    }
    else
    {
    	head.prev = node;
        node.next = head;
        haed = node;
    }
}

 

7) Shift: 앞 제거 후 값 추출

public T shift()
{
	if(head == null) return default(T);
    
    T value = head.Value;
    
    if(head == tail)
    {
    	head = null;
        tail = null;
    }
    else
    {
    	head = head.next;
        head.prev = null;
    }
    
    return value;
}

 

8) Remove: 특정 원소 제거

public void Remove(T value)
{
	Node current = head;
    
    while(current != null)
    {
    	if(current.Value.Equals(value))
        {
        	if(current.prev != null)
            	current.prev.next = current.next;
            else
            	head = current.next;
                
            if(current.next != null)
            	current.next.prev = current.prev;
            else
            	tail = current.prev;
            break;
        }
        
        current = current.next
    }
}

 

8) Print Route: 전체 노드 순서대로 출력

public void PrintRoute()
{
	Node current = head;
    
    while(current != null)
    {
    	Console.Write(current.Value + " ");
        current = current.next;
    }
    
    Console.WriteLine();
}