链表

概念

链表不需要连续的内存，通过指针将零散的内存块关联起来。

数组与链表的比较

最直观的比较是数组是连续的内存块，而链表不需要连续。

性能比较：

常见分类

常见的链表有单链表，双向链表，循环链表，双向循环链表等。

单链表

顾名思义，单链表是单方向的，链表由数据结点和后继指针组成。

特点

循环链表

双向链表

双向循环链表

特性

编码

实现一个简单的单链表。

• scala
• java
• python

/* 简单的链表 /
case class NodeT

class HiLinkedList[T >: Null] {
  var head: Node[T] = _
  var tail: Node[T] = _
  var size = 0

  //添加结点
  def add(data: T): Unit = {
    if (head == null) {
      head = Node(data, null)
      tail = head
    } else {
      val node = Node(data, null)
      tail.next = node
      tail = node
    }
    size += 1
    println(“Adding Action succeed！size is “, size)
  }

  //查询结点
  def find(data: T): Node[T] = {
    var tmp = head
    while (tmp != null) {
      println(“loop..”)
      println(tmp.data)
      if (tmp.data == data) {
        return tmp
      } else {
        tmp = tmp.next
      }
    }
    null
  }

  //删除结点
  def remove(data: T): Node[T] = {
    val node = find(data)
    var tmp = head
    if (tmp.data == data) {
      head = tmp.next
      size -= 1
    } else {
      if (node != null) {
        while (tmp != null) {
          println(“remove loop..”)
          if (tmp.next == node) {
            tmp.next = node.next
            size -= 1
            return node
          }
          tmp = tmp.next
        }
      }
    }
    node
  }
}

// todo

Todo

样例

此处使用scala实现常见的链表样例。

LRU

回文