[3.29] Linked List

정의

• 각 노드가 데이터와 포인터(reference)를 가지고 있으면서 노드들이 한 줄로 연결되어 있는 데이터 구조.

종류	특징
단방향 링크드리스트	특정 노드에서 다음노드로만 이동할 수 있는 링크드리스트
양방향 링크드리스트	특정 노드에서 앞뒤 노드로 이동할 수 있는 링크드리스트 prev와 next 두개의 포인터를 저장해야됨

★ 배열과 달리, 링크드리스트는 연속된 데이터가 아니기때문에 [ ] 로 접근이 불가능함.

각 노드는 메모리의 '어딘가'에 위치해 있으며 그것들을 포인터로 연결시켜 놓은 자료구조가 링크드리스트이다. ★

 

연산	시간
삽입	처음과 끝에서 삽입시 O(1), 그 외에 O(n)
삭제	처음과 끝에서 삭제시 O(1), 그 외에 O(n)
검색	무조건 O(n)

• 활용되는 곳 : (Head와 Tail 구현 시) 앞과 뒤에서의 삽입 삭제가 빠르므로 Queue 구현에 매우 적합한 자료구조이다.

노드의 힙 상의 위치, 위치가 어디인지 정확히 알 수없고 포인터로만 연결되어 있다.

Node Head => 링크드리스트의 첫번째 노드를 가리키는 포인터

이 노드를 중심으로 링크드리스트 순차적으로 탐색하며 삽입, 삭제, 검색을 진행하게 됨.

 

 

EX 1 ) 단일링크드리스트

using System;

namespace Study00
{
    public class Node
    {
        public int data;
        public Node next;
        public Node(int n)
        {
            this.data = n;
        }
    }

    public class SingleLinkedList
    {
        private Node head;
        private int count;

        public SingleLinkedList()
        {
            head = null;
            count = 0;
        }

        public void Add(int n)
        {
            Console.WriteLine("{0} 삽입", n);
            Node newNode = new Node(n);
            if(head == null)
            {
                head = newNode;
                head.next = null;
            }
            else
            {
                Node discover = head;
                while(discover.next != null)
                {
                    discover = discover.next;
                }
                discover.next = newNode;
                newNode.next = null;
            }
            count++;
        }

        public int GetCount()
        {
            return count;
        }
    }
}

using System;

namespace Study00
{
    public class App
    {
        public App()
        {
            SingleLinkedList list = new SingleLinkedList();
            for(int i = 0; i < 8; i++)
            {
                list.Add(i);
            }

            Console.WriteLine("List Count : {0}", list.GetCount());
        }
    }
}

 

 

2) 단일링크드리스트의 특정 위치에 삽입

using System;

namespace Study00
{
    public class Node
    {
        public int data;
        public Node next;
        public Node(int n)
        {
            this.data = n;
        }
    }

    public class SingleLinkedList
    {
        private Node head;
        private int count;

        public SingleLinkedList()
        {
            head = null;
            count = 0;
        }

        public void Add(Node newNode)
        {
            if(head == null)
            {
                head = newNode;
                head.next = null;
            }
            else
            {
                Node discover = head;
                while(discover.next != null)
                {
                    discover = discover.next;
                }
                discover.next = newNode;
                newNode.next = null;
            }
            count++;
        }

        //currentNode 뒤에 삽입
        public void Add(Node currentNode, Node newNode)
        {
            if(currentNode != null)
            {
                newNode.next = currentNode.next;
                currentNode.next = newNode;
            }
        }

        public int GetCount()
        {
            return count;
        }

        public void PrintAll()
        {
            Node current = head;
            while(current != null)
            {
                Console.Write("{0} ", current.data);
                current = current.next;
            }
        }
    }
}

using System;

namespace Study00
{
    public class App
    {
        public App()
        {
            SingleLinkedList list = new SingleLinkedList();
            Node node1 = new Node(0);
            Node node2 = new Node(1);
            Node node3 = new Node(2);
            list.Add(node1);
            list.Add(node2);
            list.Add(node3);

            Console.WriteLine("List Count : {0}", list.GetCount());

            list.Add(node2, new Node(4));
            list.PrintAll();
        }
    }
}

3번째 인덱스에 19를 삽입

 

 

3) 특정위치 노드 삭제

using System;

namespace Study00
{
    public class Node
    {
        public int data;
        public Node next;
        public Node(int n)
        {
            this.data = n;
        }
    }

    public class SingleLinkedList
    {
        private Node head;
        private int count;

        public SingleLinkedList()
        {
            head = null;
            count = 0;
        }

        public void Add(Node newNode)
        {
            if (head == null)
            {
                head = newNode;
                head.next = null;
            }
            else
            {
                Node discover = head;
                while (discover.next != null)
                {
                    discover = discover.next;
                }
                discover.next = newNode;
                newNode.next = null;
            }
            count++;
        }

        public void Erase(Node node)
        {
            Node prevNode = head;

            //리스트가 비어있을 때
            if(prevNode == null)
            {
                return;
            }

            //노드가 헤드인 경우
            if (node == head)
            {
                head = node.next;
                return;
            }

            //노드가 마지막노드인 경우
            Node discover = head;
            while (discover.next.next != null)
            {
                discover = discover.next;
            }
            if (discover.next == node)
            {
                discover.next = null;
                return;
            }

            //그 외의 중간경우
            while (prevNode.next != node)
            {
                prevNode = prevNode.next;
            }
            prevNode.next = node.next;
        }

        //currentNode 뒤에 삽입
        public void Add(Node currentNode, Node newNode)
        {
            if (currentNode != null)
            {
                newNode.next = currentNode.next;
                currentNode.next = newNode;
            }
        }

        public int GetCount()
        {
            return count;
        }

        public void PrintAll()
        {
            Node current = head;
            while (current != null)
            {
                Console.Write("{0} ", current.data);
                current = current.next;
            }
            Console.WriteLine();
        }
    }
}

1이 삭제되었다.