[자료구조]단방향(단일) 연결 리스트(1)

목표

• 단방향 연결 리스트의 정의
• 단방향 연결 리스트와 배열의 비교
• 단방향 연결 리스트에 삽입, 제거 및 순회 방법 구현

✅ 단방향 연결 리스트(Singly Linked List)란?

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 인덴스가 존재하지 않으며, 리스트에서 어딘가 접근하고 싶다면 첫 번째 노드부터 살펴봐야 한다.

🟢 노드(Node)란?

리스트에서 연결되는 하나의 데이터 정보를 말하는데 어떠한 데이터를 담을 공간과 자신의 다음 위치를 가리킬 포인터를 노드라고 한다. 이해하기 쉽게 아래의 그림을 떠올리면 된다.

 

🟢 리스트(List)란?

리스트는 위의 노드를 연결한 모양인데 꼬리에서 꼬리를 무는 형태로 그려진다. 수많은 구현 방법이 존재하지만 알아볼 방법은 head와 tail 즉, 머리(시작점)와 꼬리(끝점)라는 멤버 변수를 추가하여 삽입, 탐색, 삭제에서 유용하게 쓰일 변수들을 추가할 것이다. 

 

연결 리스트 삽입

Lists	Arrays
인덱스를 가지고 있지 않음.	인덱스로 정렬되어 있음.
각 노드들은 포인터로 연결되어 있음.	삽입과 삭제의 비용이 비쌈.
임의 접근이 허용되지 않음.(첫 노드부터 순차 탐색)	특정 인덱스에 빠르게 접근할 수 있음.

1. 데이터 삽입 - 노드를 생성하여 값은 10으로 다음 주소를 가리키는 포인터를 nullptr로 생성한 후 리스트에 담아준다. 리스트에 첫 번째로 담길 노드이기 때문에 이 노드는 head와 tail이 가리키게 된다. 가장 머리에 있는 노드라고 정하는 것이다.

 

처음 노드를 리스트에 삽입한 그림

2. 두 번째 이후 삽입부터는 20이라는 값을 가진 노드를 생성하여 현재 tail이 가리키는 0x100 노드 멤버 변수 nextNode가 nullptr을 가리켰었는데 0x200 주소를 가리키도록 연결을 시켜준다. 그 후 tail을 가장 마지막에 연결한 노드로 이동시켜 준다.

 

0x200 노드 삽입이 완료된 그림

 

3. 데이터 검색 및 출력은 리스트는 연결된 형태이기 때문에 앞에서부터 순차탐색을 이용한다. head의 위치를 변경되지 않도록 current가 노드에서부터 하나씩 nextNode를 이용하여 다음 연결된 노드로 이동하여 데이터를 검색한다. 검색을 실패하거나 출력이 완료되었을 경우 다음 노드로 이동한다.

 

Current의 이동 방향 그림

4. 데이터 삭제는 3번과 동일하게 순회하면서 다음 위치를 삭제해 버리면 다다음 위치를 접근할 수 없게 되어버린다. 바로 아래의 그림을 보면 이와 같은 상황을 볼 수 있다. 정상적으로 삭제를 하려면 0x200 노드를 삭제하기 전 0x100 노드의 nextNode를 0x300에 연결을 시켜준 후에 삭제를 해야 한다.

 

연결된 노드를 바로 삭제하면 접근할 0x100 노드의 nextNode를 0x300 노드로 연결한 후 정상적으로 삭제하는 그림수 없는 문제가 발생!!

구현

앞서 설명한 내용들을 토대로 코드로 구현해 보자. 코드로 구현하기 전에 구현할 내용을 다시 정리해 본다.

 

🟢 1. Push

• 값을 받아서 새로운 노드를 만든다.
• 만약 리스트에 head 프로퍼티가 존재하지 않으면, head와 tail를 새롭게 생성된 노드로 설정한다.
• 그렇지 않으면, tail이 가리키고 있는  'next' 프로퍼티(포인터)가 새로운 노드를 가리키도록 하고, 리스트의 tail 프로퍼티를 새로운 노드를 가리키도록 한다. 
• 길이를 1씩 늘린다.

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val) {
        let newNode = new Node(val);;
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
}
let list = new SinglyLinkedList()

실행 결과

🟢 2. Pop

연결 리스트의 맨 마지막 노드를 제거한다. 마지막 노드를 제거하는 것은 쉽지만, tail을 업데이트하는 것은 쉽지 않다.

• 리스트에 노드가 없다면 undefined를 반환한다.
• tail에 도달할 때까지 리스트를 반복한다. 테일 바로 전 노드를 찾아야 한다.
• 마지막에서 두 번째 노드의 next 속성을 null로 설정한다.
• 마지막에서 두 번째 노드를 tail로 설정한다.
• 리스트의 길이를 1 감소시킨다.
• 제거된 이전 tail 노드의 값을 반환한다.

class Node {
    constructor(val) {
        this.val = val;
        this.next = null
    }
}

class Singly {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    pop() {
        // node가 없을 경우 undefined 반환 
        if(!this.head) return undefined;
        let cur = this.head;
        let newTail = cur;
          // cur.next가 없을 때까지 반복. cur가 tail에 도달하면 next가 없음.
          while (cur.next) {
            newTail = cur;
            cur = cur.next;
          }
        // cur이 tail에 도달하고 기존 tail을 변경
        this.tail = newTail;
        // 기존 tail을 null
        this.tail.next = null;
        this.length--;
          if(this.length === 0) {
            this.head = null;
            this.tail = null;
          }
        return cur;
    }
}

let list = new Singly()
list.push('Hello');
list.push('Goobye');
list.push('!');

🟢 3. Shift

연결 리스트의 앞에서 노드를 제거한다. 

• 리스트에 노드가 없다면 undefined를 반환한다.
• 현재의 head 속성을 변수에 저장한다.
• head 속성을 현재 head의 next 속성으로 설정한다. 
• 리스트의 길이를 1 감소시킨다.
• 제거된 이전 head  노드의 값을 반환한다.

class Node {
    constructor(val) {
        this.val = val;
        this.next = null
    }
}

class Singly {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    shift() {
        if(!this.head) return undefined;
        let curHead = this.head;
        this.head = curHead.next;
        this.length--;
        if(this.length === 0) {
            this.tail = null;
        }
        return curHead
    }
}

🟢 4. Unshift

연결 리스트의 맨 앞에 노드를 추가한다.

• 리스트의 시작 위치에 추가하려는 노드의 값을 인자로 받는다.
• 전달받은 값으로 새로운 노드를 만든다.
• head 속성이 리스트에 없다면, head와 tail을 새롭게 생성된 노드로 설정한다.
• 있을 경우, 새롭게 생성된 노드의 next 속성을 리스트 현재의 head 속성으로 설정한다.
• 새롭게 생성한 노드를 리스트의 head 값으로 설정하고, length + 1 한 다음 리스트를 반환한다.

class Node {
    constructor(val) {
        this.val = val;
        this.next = null
    }
}

class Singly {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    unShift(val) {
        let newNode= new Node(val);
        if(!this.head) {
           this.head = newNode;
           this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;  
        }
        this.length++;
        return this;
    }
}

let list = new Singly()

 

👉 2편 보러 가기