[자료구조] 단일 연결 리스트(Singly Linked List)

단일 연결 리스트 

• 단반향으로 노드들을 연결한 간단한 자료 구조

 

 

구현

 

 // 연결 리스트의 노드 클래스
    public class SinglyLinkedListNode<T>
    {
        public T Data { get; set; }
        
        public SinglyLinkedListNode<T> Next { get; set; }

        public SinglyLinkedListNode(T data) {
            this.Data = data;
            this.Next = null;
        }

    }

    public class SinglyLinkedList<T> {
        // head를 사용하여 전체 리스트를 순차적으로 엑세스
        private SinglyLinkedListNode<T> head;

        public void Add(SinglyLinkedListNode<T> newNode) {
            if (head == null) { //리스트가 비어 있으면
                head = newNode;
            }
            else { //리스트가 비어 있지 않으면
                var current = head;
                while (current != null && current.Next != null) {
                    current = current.Next;
                }

                current.Next = newNode;
            }
        }

        public void AddAfter(SinglyLinkedListNode<T> current, SinglyLinkedListNode<T> newNode) {
            if (head == null || current == null || newNode == null) {
                throw new InvalidOperationException();
            }

            newNode.Next = current.Next;
            current.Next = newNode;

        }

        public void Remove(SinglyLinkedListNode<T> removeNode) {
            if (head == null || removeNode == null) {
                return;
            }

            //삭제할 노드가 첫 노드일 경우
            if (removeNode == head) {
                head = head.Next;
                removeNode = null;
            }
            else { // 첫 노드가 아닐 경우 해당 노드를 검색하여 삭제
                var current = head;

                //삭제할 노드의 바로 이전 노드를 검색
                while (current != null && current.Next != removeNode) {
                    current = current.Next;
                }

                if (current != null) {
                    //이전 노드의 Next에 삭제노드의 Next를 할당
                    current.Next = removeNode.Next;
                    removeNode = null;
                }
            }
        }

        // 특정 위치 인덱스에 있는 노드를 리턴
        // 인덱스가 연결리스트를 벗어나면 null 리턴
        // O(n)의 검색시간을 갖는다.
        public SinglyLinkedListNode<T> GetNode(int index) { 
            var current = head;
            for (int i = 0; i < index && current != null; i++) {
                current = current.Next;
            }

            //index가 리스트 카운트보다 크면 리턴
            return current;
        }

        public int Count() {
            int cnt = 0;

            var current = head;
            while (current != null) {
                cnt++;
                current = current.Next;
            }

            return cnt;
        }
    }

 

메인메소드

 static void Main(string[] args) 
        {

            Console.WriteLine("Hello");

            /*연결 리스트*/
            var list = new SinglyLinkedList<int>();

            // 리스트에 요소 추가
            for (int i = 0; i < 5; i++) {
                list.Add(new SinglyLinkedListNode<int>(i));
            }

            //index가 2인 요소 삭제
            var node = list.GetNode(2);
            list.Remove(node);

            // index가 1인 요소 가져오기
            node = list.GetNode(1);

            //index 1인 요소 뒤에 99 삽입
            list.AddAfter(node, new SinglyLinkedListNode<int>(99));

            //리스트 카운트
            int cnt = list.Count();

            //리스트 출력
            for (int i = 0; i < cnt; i++) {
                var n = list.GetNode(i);
                Console.WriteLine(n.Data);
            }

        }

 

결과

 

 

장/단점

배열과 비교했을 때 자료의 접근은 더 빠르나 삽입이나 삭제 시 느리다. 

데이터 공간을 미리 할당하지 않아도 되지만 연결을 위한 별도의 공간이 필요하다.