자료구조 - 한방향 연결리스트, 양방향 연결리스트

1. 연결리스트

---

1) 개념

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하나의 전체적인 자료구조를 이룸.

링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않음

자료의 크기를 동적으로 조절해 메모리의 효율적인 사용 가능.(추가 삭제 빠름)

2) 노드

연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위

- 구성요소

• 데이터 필드 : 원소의 값
• 링크 필드 : 다음 노드의 주소 ( 마지막 노드는 링크 값을 null로 가짐)

- 헤드 : 리스트의 처음 노드를 가리키는 레퍼런스

 

 

 

 

 

2. 한방향 연결리스트

---

1) 연결구조

노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가짐

헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킴

최종적으로 NULL을 가리키는 노드가 리스트의 가장 마지막 노드

2) 조회연산 : O(N)

- 원하는 값이 나올 때까지 next 노드를 타고 조회

3) 삽입연산

- 리스트 사이에 새로운 노드 연결 시

• 새로운 노드를 다음 노드에 먼저 연결
• 이전 노드를 새로 추가한 노드에 연결
• 다음 노드에 접근하기 위해서는 직전 노드를 통해서 접근할 수 밖에 없으므로 다음 노드부터 연결하는 것
• 이전, 다음 노드를 알고 있다면 O(1)

- AddFront (맨 앞에 삽입) : O(1)

• 헤드 노드가 있다면 그 앞에 삽입
• 없다면 헤드 노드로 삽입

- AddBack (맨 뒤에 삽입) : O(N)

• 헤드 노드부터 시작해서 다음 노드가 null인 노드까지 찾아가기
• 마지막 노드가 null이면 맨 뒤란 뜻이므로, 마지막 노드의 next를 삽입하려는 노드의 주솟값을 가리키도록 변경

4) 삭제연산

- popFront (맨 앞 삭제) : O(1)

• 지울 노드가 있으면(헤드가 존재하면) head 값을 head의 next로 변경

- popBack (맨 뒤 삭제) : O(N)

• tail 노드의 직전 노드를 찾아가서, 직전 노드의 next를 none 처리

5) Java로 구현해보기

- Node

public class Node {
    public int data; // 데이터
    public Node next; // 다음 노드의 주소값

    public Node(int data) {
        this.data = data;
        this.next = null;

    }

}

- SinglyLinkedList

public class SinglyLinkedList {
    // 연결리스트는 head만 저장하고 있으면 됨
    public Node head;

    public SinglyLinkedList() {

    }

    // 가장 마지막에 추가 : addToEnd
    // 가장 처음에 추가 : addToStart
    // 특정 값을 갖는 노드 다음에 추가: addAfter
    // 특정 값을 갖는 노드를 반환: getNode
    // 가장 마지막에 있는 노드 삭제: deleteLast
    // 가장 처음에 있는 노드 삭제: deleteStart
    // 특정 값을 갖는 노드 다음 노드 삭제: deleteAfter
    // 리스트를 순회해서 출력: printList

    public void addToEnd(int data) {
        // 새로운 노드를 생성
        Node n = new Node(data);

        // 리스트가 비어있는지 여부 먼저 체크
        if(head == null) { // 리스트가 비어있다면
            head = n;
        } else {
            // 가장 마지막 노드 찾기
            Node curr = head; // 임시 변수 curr에다가 가장 첫번째 노드의 주소값을 저장해 놓고 시작
            while(curr.next != null) { // 그 다음 노드가 있다면
                curr = curr.next; // 그 다음 노드로 이동
            }
            // while문이 끝났다면?
            // curr.next == null
            // curr => 가장 마지막 노드를 가리키고 있는 상태


            // 가장 마지막 노드의 다음에 새로운 노드를 추가
            curr.next = n;
        }
    }

    public void addToStart(int data) {
        // 새로운 노드 만들기
        Node n = new Node(data);
        // 현재 첫번째 노드는 head를 통해서만 접근 가능..
        // 현재 첫번째 노드는 두번째 노드가 되어야 함..
        // 새로운 노드.next <= 현재 첫번째 노드의 주소값(head)
        n.next = head;
        // head가 새로운 노드 가리키도록 하기
        // head <= 새로운 노드의 주소값
        head = n;
    }

    // target이라는 값을 갖는 노드의 주소값을 반환
    public Node getNode(int target) {
        Node curr = head;
        while(curr != null) {
            if(curr.data == target) {
                return curr;
            }
            curr = curr.next;
        }
        return null; // 노드를 찾지 못했다면 null을 반환
    }

    // target이라는 값을 갖는 노드를 찾아서
    // 그 다음에 data라는 값을 갖는 노드 삽입
    public void addAfter(int target, int data) {
        Node targetNode = getNode(target);
        if(targetNode != null) { // 노드를 찾았다면
            Node n = new Node(data);
            n.next = targetNode.next;
            targetNode.next = n;
        }

    }


    public void printList() {
        Node curr = head;
        System.out.print("LinkedList[head:");

        while(curr != null) {
            System.out.print(curr.data+"->");
            curr = curr.next;
        }
        System.out.println("]");
    }

}

3. 양방향 연결리스트

---

1) 연결구조

노드가 두개의 링크 필드를 가져 다음노드와 이전노드를 가리키고 있는 연결구조를 가짐

따라서 한방향연결리스트는 previous 노드를 찾기 위해 처음 head부터 다시 연결을 타고 조회를 하던 것과 달리, 바로 직전 노드를 조회할 수 있음.

원형 양방향 연결리스트(Circularly Double LinkedList) : tail이 head를 가리키도록 head의 previous link가 tail을 가리키도록 하는 형태

원형 양방향 연결리스트는 삽입, 삭제 연산들이 심플해짐

아래 연산들은 원형 양방향 연결리스트를 가정하고 진행할 것.

원형 양방향은 시작점을 구분할 수 없으므로 빈 dummy node를 두고 이 노드를 마커 역할로 사용할 것.

 

2) Splice 연산 : O(1)

a, b, x 노드에 대하여 아래 조건을 충족해야 한다.

조건1) a의 next를 따라가다 보면 b가 존재해야 한다.

조건2) a와 b 노드 사이에는 head노드가 존재하지 않는다.

위 조건을 충족한 상태에서, a부터 b노드까지를 cut해서 어딘가에 존재하는 x노드 다음에 삽입하는 연산

- 연산과정

(노드 이름에 p를 붙이면 previous node, n을 붙이면 next node라 하자)

• ap의 next를 bn으로 지정
• bn의 previous를 ap로 지정
• x의 next 를 a로 지정
• a의 previous를 x로 지정
• b의 next를 xn으로 지정
• xn의 previous를 b로 지정

 

3) 삽입 연산 : O(1)

- moveAfter(a, x)

• 노드 a를 x 다음으로 이동
• splice(a, a, x)

- moveBefore(a, x)

• a를 x전으로 이동
• splice(a, a, x.prev)

- insertAfter(x, key)

• key를 가지는 새로운 node 생성
• moveAfter(Node(key), x)

- insertBefore(x, key)

• moveBefore(Node(key), x)

- pushFront(key)

• insertAfter(head, key)

- pushBack(key)

• insertBefore(head, key)

 

4) 탐색 연산 : O(N)

head부터 다음 노드를 조회하는데, 다음 노드가 헤드노드가 아닐 때까지 탐색

 

 

5) 삭제 연산 : O(1)

remove(x)

• 특정 노드(x) 를 삭제하고 싶을 때 
• x가 더미노드이거나 head를 지우려고 한다면 아무것도 하면 안 됨.
• 아닐 경우, xp의 next를 xn으로, xn의 previous를 xp를 가리키도록 변경

 

삭제, 삽입을 하기 위한 목표 노드를 알려주므로 상수의 시간복잡도를 가지긴 하지만, 탐색하려면 O(N)이 필요하긴 할 것.

 

 

---

본 게시글은 한국외국어대학교 컴전학부의 신찬수 교수님의 유튜브 강의를 보고 학습한 내용을 작성한 학습기록입니다.

자료구조 과목 소개 - YouTube