【Day4】[资料结构]-链结串列Linked List-实作

链结串列(Linked List)建立的方法

• append: 在尾部新增节点
• insertAt: 在特定位置插入节点
• removeAt: 删除特定位置节点
• remove: 删除特定资料节点
• indexOf: 回传第一个出现指定资料的节点位置，空值则回传-1
• isEmpty: 确认是否为空串列
• size: 串列的长度
• print: 印出串列所有资料

链结串列的介绍可以参考此篇。

JavaScript(单向链结串列为例)

//Linked List

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

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  //在尾部插入节点
  append(data) {
    let newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while(current.next){
        current = current.next
      }
      current.next = newNode 
    }
    this.length += 1;
  }

  //特定位置插入节点
  insertAt(index, data) {
    // 确认给的位置是否超出实际总数。
    if (index < 0 || index >= this.length) {
      return null;
    }

    let newNode = new Node(data);
    let current = this.head;
    let previous;
    let count = 0;
    if (index == 0) {
      this.head = newNode;
      newNode.next = this.head;
    } else {
      while(count != index){
        count ++;
        previous = current;
        current = current.next;
      }
      newNode.next = current;
      previous.next = newNode;    
    }
    this.length += 1;
  }

  //删除特定位置节点
  removeAt(index) {
    if (index < 0 || index >= this.length){
        return false;
    }
    let current = this.head;
    let previous;
    let count = 0;
    if (index === 0) {
      this.head = current.next;
    } else {
      while(count != index){
        count ++;
        previous = current;
        current = current.next;
      }
      previous.next = current.next
    }
    this.length -= 1;
  }
  
  //删除特定节点
  remove(data) {
    let current = this.head;
    let previos = null;
    while (current != null) {
      if (current.data === data) {
        if (previos == null) {
          this.head = current.next;
        } else {
          previos.next = current.next;
        }
        this.length -= 1;
      }
      previos = current;
      current = current.next;
    }
  }

  //回传第一个出现此资料节点的位置，若空值则回传-1
  indexOf(data) {
    let currNode = this.head;
    let count = 0;
    while (currNode) {
      if (currNode.data === data) {
          return count;
      }
      count += 1;
      currNode = currNode.next;
    }
    return -1;
  }
  
  //是否为空串列
  isEmpty() {
    return this.length === 0;
  }
  
  //串列长度
  size() {
    return this.length;
  }

  //印出串列所有资料
  print() {
    const temp = [];
    let currNode = this.head;
    while (currNode) {
      temp.push(currNode.data);
      currNode = currNode.next;
    }
    return temp.join(', ');
  }
}


let ll = new LinkedList();
console.log(ll.isEmpty());//true
ll.append(10);
ll.append(20);
console.log(ll.isEmpty());//false
console.log(ll.print())//"10, 20"
ll.insertAt(1,60);
console.log(ll.print())//"10, 60, 20"
ll.append(20);
console.log(ll.print())//"10, 60, 20, 20"
ll.removeAt(2)
console.log(ll.print())//"10, 60, 20"
ll.remove(20)
console.log(ll.size())//2
console.log(ll.print())//"10, 60"

Python(单向链结串列为例)

#Linked List

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self, head=None):
        self.head = head

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)

    def insertAt(self, index, data):
        if index < 0 or index >= self.size():
            return
        node = Node(data)
        current = self.head
        previous = None
        count = 0
        if index == 0:
            self.head = Node(data, node)
        else:
            while count != index:
                count += 1
                previous = current
                current = current.next
            new_node = Node(data, previous.next)
            previous.next = new_node

    def removeAt(self, index):
        if index < 0 or index >= self.size():
            return
        current = self.head
        previous = None
        count = 0
        if index == 0:
            self.head = current.next
        else:
            while count != index:
                count += 1
                previous = current
                current = current.next
            previous.next = current.next

    def remove(self, data, all=False):
        current = self.head
        previous = None
        while current:
            if current.data == data:
                if previous:
                    previous.next = current.next
                    current.next = current
                else:
                    self.head = current.next
                if not all:
                    return
            else:
                previous = current
                current = current.next

    def indexOf(self, data):
        node = self.head
        count = 0
        while node:
            if node.data == data:
                return count
            count += 1
            node = node.next

    def isEmpty(self):
        return self.head is None

    def size(self):
        count = 0
        node = self.head
        while node:
            count += 1
            node = node.next
        return count

    def print(self):
        if not self.head:
            print(self.head)
        node = self.head
        while node:
            end = " -> "
            print(node.data, end=end)
            node = node.next

ll = LinkedList()
print(ll.isEmpty())#True
ll.append(10)
ll.append(20)
print(ll.isEmpty())#False
print(ll.print())#10 -> 20 -> None
ll.insertAt(1,60)
print(ll.print())#10 -> 60 -> 20 -> None
ll.append(20)
print(ll.print())#10 -> 60 -> 20 -> 20 -> None
ll.remove(20)
print(ll.print())#10 -> 60 -> 20 -> None
ll.removeAt(1)
print(ll.print())#10 -> 20 -> None
ll.remove(20)
print(ll.size())#1
print(ll.print())#10 -> None

链结串列的介绍可以参考此篇。