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

rlorxl·2022년 2월 15일
0

연결 리스트

연결 리스트는 노드(Node)라는 객체로 이루어져 있고 각 노드가 데이터(data field)와 포인터(linked field)를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

자료가 연결되어 있어 새로운 자료를 앞쪽에 추가,삭제 시 유용하게 사용할 수 있다. 하지만 특정 자료를 불러올 때는 무조건 앞쪽부터 순회하며 찾는 과정을 거치기 때문에 이때는 배열을 사용하는 편이 효율적이다.

연결 리스트에는 데이터를 저장하는 역할을 하는 프로퍼티(여기서는 data)와 다음 노드의 위치를 가리키는 포인터 역할을 하는 프로퍼티(next)가 각각 존재한다.

data - 데이터를 저장하는 공간
pointer - 다음 주소를 가리키는 공간(next address)

[data | next]
	Node

head - 가장 최초의 주소를 가리키는 노드
tail - 마지막 노드 - 포인터는 'null'을 가리킨다.

head -> [ 0 | ]->[ 0 | ]->[ 0 | ]-> null
		  Node	   Node		Node

코드

// Node(): data와 point를 가지고 있는 객체
function Node(data) {
    this.data = data;
    this.next = null;
}
// LinkedList(): head와 length를 가지고 있는 객체
function LinkedList() {
    this.head = null;
    this.length = 0;
}

구현 메서드

노드 개수 / 비어있는지 확인 / 노드 출력 : size() isEmpty() printNode()
노드 추가 : append() insert()
노드 삭제 : remove() removeAt()
데이터 위치 확인 : indexOf()

size(), isEmpty()

size는 length와 같고 비어있는지 확인을 위해 isEmpty라는 메서드를 정의한다.

LinkedList.prototype.size = function(){
    return this.length;
}
LinkedList.prototype.isEmpty = function(){
    return this.length === 0;
}

printNode()

노드를 출력하기 위한 메서드이다. LinkedList를 탐색을 하면서 데이터를 찍어주고, 마지막엔 null을 출력한다. 개행없이 옆으로 출력하고, 화살표를 그려서 데이터의 연결이 가시적으로 보이도록 되어있다.

LinkedList.prototype.printNode = function(){
    for(let node = this.head; node != null; node = node.next){
        process.stdout.write(`${node.data} -> `);
    }
    console.log('null');
}

노드 추가

  • 가장 마지막 위치에 노드를 추가.
  • 새로운 노드를 생성하고 current라는 변수에 시작노드를 할당한다.
  • 만약 head가 없다면 head는 바로 추가하는 노드가되고 length를 업데이트하고 끝난다.
  • head가 존재한다면 가장 마지막 노드를 찾을때까지 노드를 앞쪽으로 이동시키는걸 반복한 후 가장 마지막에 노드를 추가한다.

코드

LinkedList.prototype.append = function(value){
    let node = new Node(value),
        current = this.head;

    if(this.head === null){
        this.head = node;
    } else {
        while(current.next != null){
            current = current.next;
        }
        current.next = node;
    }

    this.length++;
}

출력해보기

let ll = new LinkedList();

ll.append(1);
ll.append(10);
ll.append(100);
ll.printNode();

결과

1 -> 10 -> 100 -> null

지정한 위치에 노드 추가

  • 지정한 위치에 노드를 추가하기 위해 매개변수로 value와 함께 position을 받는다.
  • position이 음수이거나, 노드 길이를 벗어나면 리스트에 추가하지 않겠다는 범위를 체크하는 조건문을 생성하고 새로운 노드를 생성한다.
  • index를 0으로 초기화하고, 이전 노드의 값을 prev라는 변수가 나타내도록 한다.
  • 포지션 값이 존재하지 않을 때는 현재 데이터를 뒤로 보내며 추가한 노드가 head자리에 온다. 포지션 값이 존재하면 데이터를 순회하며 노드가 추가될 위치를 찾은 후(while문) 찾은 position에 노드를 추가한다.
[ prev | ]<-[ new node | ]<-[ current | ]

코드

LinkedList.prototype.insert = function(value, position = 0){
    // 범위체크 (position이 음수이거나, 길이를 벗어나면 리스트에 추가하지 않는다)
    if(position < 0 || position > this.length){
        return false;
    }

    let node = new Node(value),
        current = this.head,
        index = 0,
        prev; //이전 노드 값

    // 포지션이 없을 때
    if(position === 0){
        node.next = current;
        this.head = node;

    // 포지션이 있을 때
    } else {
        while(index++ < position){
            // position=1일때:코드 1회수행(index가 0부터 시작이므로), position=3일때:코드 3회수행
            prev = current;
            current = current.next;
        }
        node.next = current; 
        prev.next = node; 
    }

    this.length++;

    return true;
}

출력해 보기

ll.insert(1);
ll.insert(10);
ll.insert(100);
ll.printNode();

ll.insert(2,1);
ll.insert(3,3);
ll.printNode();

결과

100 -> 10 -> 1 -> null
100 -> 2 -> 10 -> 3 -> 1 -> null

노드 삭제

  • value값이 있는 데이터를 찾아 노드를 삭제한다.
  • 반복문을 통해 value로 들어온 데이터가 있는지 탐색한다. 조건은 current데이터에 value가 있고 current가 가리키는 곳이 null (마지막지점)이 아닐때까지 prev, current가 점점 앞으로 이동하며 탐색을 한다.
  • 찾는 value가 없으면 null을 반환하고 value값이 있다면 prev가 가리키는 노드의 다음 주소가 current가 가리키는 다음 주소가 된다. (current였던 노드의 주소는 참조되지 않으며 무시가 되는 것으로 사실상 삭제처럼 동작한다.)
LinkedList.prototype.remove = function(value){
    // 초기화
    let current = this.head, // 최초 노드
        prev = current;

    while(current.data != value && current.next != null){
        prev = current;
        current = current.next;
    }

    // value가 없으면 끝낸다
    if(current.data != value){
        return null;
    }
    // value가 있을 때
    if(current === this.head){ // current가 가장 최초 노드일때 수행됨.
        this.head = current.next;
    } else { 
        prev.next = current.next; 
    }

    this.length--; 
    return current.data;
}

출력해 보기

console.log(ll.remove(1000));
ll.printNode();
console.log(ll.remove(1));
ll.printNode();
console.log(ll.remove(2));
ll.printNode();
console.log(ll.remove(100));
ll.printNode();

결과

null
100 -> 2 -> 10 -> 3 -> 1 -> null
1
100 -> 2 -> 10 -> 3 -> null
2
100 -> 10 -> 3 -> null
100
10 -> 3 -> null

지정위치 노드 삭제

  • 매개변수로 받은 position값을 기반으로 노드의 위치를 찾아 삭제한다. (position의 디폴트는 0으로 지정한다.)
  • position이 0이면 head가 current의 다음노드를 가리키고 current 노드는 삭제된다. 아닌 경우에는 인덱스 횟수만큼 이동시키고 current를 참조하는 링크를 없앤다.
LinkedList.prototype.removeAt = function(position = 0){
    if(position < 0 || position >= this.length){
        return null;
    }

    let current = this.head,
        index = 0,
        prev;

    if(position === 0){
        this.head = current.next;
    } else {
        while(index++ < position){
            prev = current;
            current = current.next;
        }
        prev.next = current.next;
    }

    this.length--;
    return current.data;
}

출력해 보기

console.log(ll.removeAt(1000));
ll.printNode();
console.log(ll.removeAt(1));
ll.printNode();
console.log(ll.removeAt(2));
ll.printNode();
console.log(ll.removeAt());
ll.printNode();

결과

null
100 -> 2 -> 10 -> 3 -> 1 -> null
2
100 -> 10 -> 3 -> 1 -> null
3
100 -> 10 -> 1 -> null
100
10 -> 1 -> null

노드 위치 확인

  • value값을 가지는 노드의 위치를 확인한다.
  • 인덱스를 이동하며 데이터가 같은지 판단한다. 맞으면 해당 인덱스 값을 반환한다.
LinkedList.prototype.indexOf = function(value){
    let current = this.head,
        index = 0;
    // current가 null이 아닐때까지 반복
    while(current != null){
        if(current.data === value){
            return index;
        }

        index++;
        current = current.next;
    }
	// 값이 없으면 -1을 반환
    return -1;
}

removeAt + indexOf

indexOf와 removeAt을 같이 사용해서 remove의 역할을 하도록 만들 수 있다.

LinkedList.prototype.remove2 = function(value){
    let index = this.indexOf(value);
    return this.removeAt(index);
}

출력해보기

console.log(ll.remove(1000));
ll.printNode();
console.log(ll.remove2(1));
ll.printNode();
console.log(ll.remove2(2));
ll.printNode();
console.log(ll.remove2(100));
ll.printNode();

결과

null
100 -> 2 -> 10 -> 3 -> 1 -> null
1
100 -> 2 -> 10 -> 3 -> null
2
100 -> 10 -> 3 -> null
100
10 -> 3 -> null

참조
https://overcome-the-limits.tistory.com/16
https://sycho-lego.tistory.com/17

profile
즐겜하는거죠

0개의 댓글