[ DS ] Linked List ( by using Python )

연결 리스트란 ?

  

연결리스트는 선형 자료구조로써, 연속적으로 메모리에 존재 하지 않고, 포인터를 통해서 다음 인덱스를 나타냅니다.

  

    

연결 리스트의 특징

  

1. 탐색 및 수정

• Linked List는 인덱스가 없어, 처음부터 탐색을 시작 하기 때문에 O(k) 이다. ( = k는 탐색 하는 대상의 위치 )
  • 예시로 [ 철수, 영희, 민수, 동현 ] 으로 구성된 Linked List에서 동현을 찾는다고 가정해보자.
  • 배열의 경우는 인덱스의 값을 통해 빠르게 접근이 가능하지만, Linked List는 철수 -> 영희 -> 민수 -> 동현을 거쳐야 알 수 있다.

2. 삽입 및 삭제

• Linked List의 삽입 삭제는 이전의 next를 제거하고, 이어주는 기능만을 수행하면 되기에 O(1) 이다.

    

연결 리스트 구현

  

Node 구현

• 연결리스트의 노드는 자신의 값과, 다음 노드를 가리키는 참조 값을 이루어져있다.

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

  

Linked List 구현 + 삽입

class SingleLinkedList {
  // Linked List 에서는 head & taill 에 대한 정보 만을 저장한다.
  constructor() {
    this.head = null;
    this.tail = null;
    
  }
  
  
  append(newValue) {
    const newNode = new Node(newValue);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  
}

  

Node idx 알아내기

  // N만큼의 시간이 소요된다.
  find(value) {
    let curNode = this.head;
    // 특정 값을 찾을 때 까지 while-loop
    while (curNode.value !== value) {
      curNode = curNode.next;

      if (curNode === null) {
        return console.log("Can't find this value in Linked List");
      }
    }

    return curNode;
  }

 

   

특정 자리 뒤로 삽입

  // 탐색을 방지 하기 위해서, 삽입 하고자 하는 위치를 Parameter로 전달
  insert(node, newValue) {
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }

 

 

삭제

  remove(value) {
    let prevNode = this.head;

    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }

  

  

 

전체 코드

// 전체 코드

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

class SingleLinkedList {
  // Linked List 에서는 head & taill 에 대한 정보 만을 저장한다.
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // N만큼의 시간이 소요된다.
  find(value) {
    let curNode = this.head;
    // 특정 값을 찾을 때 까지 while-loop
    while (curNode.value !== value) {
      curNode = curNode.next;

      if (curNode === null) {
        return console.log("Can't find this value in Linked List");
      }
    }

    return curNode;
  }

  append(newValue) {
    const newNode = new Node(newValue);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  // 탐색을 방지 하기 위해서, 삽입 하고자 하는 위치를 Parameter로 전달
  insert(node, newValue) {
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }

  //
  remove(value) {
    let prevNode = this.head;

    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }

  display() {
    let curNode = this.head;
    let displayString = "[";

    while (curNode !== null) {
      displayString += `${curNode.value}, `;
      curNode = curNode.next;
    }

    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }
}

const linkedList = new SingleLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);
linkedList.display();
linkedList.find(3);
linkedList.remove(3);
linkedList.insert(linkedList.find(2), 10);
linkedList.display();