分类目录归档:数据结构

再回首数据结构—链表

  链表与数组一样同为线性数据结构,不少编程语言也自带了链表的实现,链表可以存放不同数据类型的数据;
  与数组不同,数组占用内存结构必须为连续,而链表则不需要内存空间为连续的;链表由多个节点连接而成,每个节点除了存储当前节点的值外还存有指向链表中下一个节点的地址;链表也有多种结构:单链表、双向链表、循环链表等等;
  单链表的数据结构如下所示:

enter image description here

  通过上图可以看出链表的基本结构,每个节点由值与地址两部分组成,地址存储链中下一个节点的地址,由此将所有 节点串联起来;

链表的优势

  相比数组不需要连续的内存空间,系统存在内存碎片也可使用链表;
  如需要申请200MB大小的数组,但当前内存中没有足够大连续的内存空间,就算当前可用内存有200MB也不会申请成功;
  而链表则不同,只要可用内存有200MB就可使用,不需要内存块为连续的它通过指针将节点(内存块)串联起来;
  之前所说的动态数组其实只是伪动态当静态数组满时通过内部的resize创建一个新静态数组进行扩容,而链表为真动态;

  1、 数组插入删除
  数组为保持内存的连续性插入删除需要移动N个元素,时间复杂度为O(n)
  2、 链表插入删除
  链表未使用连续内存空间则也不需要移动元素,所以速度会比数组快不少;
  由于链表使用的不时连续存储空间,所以不能像数组一样通过寻址公式就能访问到指定的元素,需要通过一个一个遍历每个节点才能找到对应的节点,所以数组的随机访问时间复杂度为O(1),而链表为O(n);

enter image description here

插入删除 O(n) O(1) 随机访问 O(1) O(n)

链表插入与删除

  链表的插入与删除比数组快不少,链表并非使用连续的内存空间,不需要去维护内存连续性,就插入与删除而言双向链表又比单链表性能要好;

  要在节点c后插入O节点,需要从第一个节点开始遍历链表知道找到节点c然后执行如下操作:

enter image description here

 O.next = c.next
 c.next = O

  删除节点d需要找到该节点的前一个节点,找到节点c后执行如下操作:

enter image description here

 c.next = d.next
 d.next = null

  由于单链表只存储下一个节点地址需要遍历链表节点才能找到前一个节点,而双向链表既存储了下一个节点地址又存储上一个节点地址,双向链表性能比单链表要好;

链表要点

  1、如上面所说的插入元素在c节点后插入O节点,操作时需要注意要先执行O指向c的下一个节点,当一上来就执行c.next=O此时链表c节点后的节点就断开丢失了;
  2、链表删除时需要注意要释放节点,如上示例:执行c.next=d.next后如未执行d.next=null此时d节点就未被释放掉,虽然链表中未有节点指向该节点,但该节点并未断开连接;
  3、使用头节点简化插入、删除操作;

下面为使用Golang实现的链表

 type Node struct {
    e    interface{}
    next *Node
 }
 type LinkedList struct {
    head *Node
    size int
 }

 /**
 往链表头添加元素
  */
 func (l *LinkedList) AddFirst(e interface{}) {
    l.Add(0, e)
 }

 func (l *LinkedList) Add(index int, e interface{}) error {
    if index < 0 || index > l.size {
        return errors.New("Add failed. Illegal index.")
    }
    prev := l.head
    for i := 0; i < index; i++ {
        prev = prev.next
    }
    prev.next = &Node{e: e, next: prev.next}
    l.size++
    return nil
 }

 /**
 nil->3  2  1
 查找指定索引节点
  */
 func (l *LinkedList) Find(index int) *Node {
    cur := l.head.next
    for i := 0; i < index; i++ {
        cur = cur.next
    }
    return cur
 }

 /**
 删除指定位置节点
  */
 func (l *LinkedList) Remove(index int) error {
    node := l.head.next
    if node != nil {
        if prev := l.Find(index - 1); prev != nil {
            node = prev.next
            if node != nil {
            prev.next = node.next
            node.next = nil
        }
    }
}
return nil
 }

再回首数据结构—数组(Golang实现)

  数组为线性数据结构,通常编程语言都有自带了数组数据类型结构,数组存放的是有个相同数据类型的数据集;
  为什么称数组为线性数据结构:因为数组在内存中是连续存储的数据结构,数组中每个元素最多只有左右两个方向有相邻的元素;数组中的每个元素都有一个索引(或称下标)标识,这个索引在编程语言中通常都是从0开始,通过索引可访问到数组中对应的元素;数组的数据结构如下所示:

enter image description here

数组的优势

  从上文中我们知道数组在内存中是连续存储的也就是说数组中元素在内存块为连续,此时我们利用此特性通过索引快速访问数据元素;因此也称数组支持随机访问
  下面我们通过一个示例来说明数组的随机访问特性;

  在Go中定义一个长度为7的数组:
  var array [7] int
  此时我们可以通过索引随机访问数组中元素如:array[5]即可访问到数组中的第六个元素,这背后又是怎样的呢,上面我们说过数组在内存中的存储结构是连续的上面我们定义的数组结构如下所示:

enter image description here

  此处假设该数组内存空间首地址为:000,由于该数据类型为int因此每个数据元素占4个字节,所以上面定义7个长度数组占用的内存地址为:000~024连续的地址空间;所以通过下面的计算公式即可实现数组的随机访问,比如访问数组中第五个元素内存地址的计算公式如下:

  所访问元素内存地址=数组首地址 + index * 数据类型大小
  array[5]内存地址 = 000 + 5 * 4
  所以数组的优势为:1、简单;2、支持随机访问,通过索引随机访问时间复杂度为O(1)

数组插入与删除

  数组的插入与删除其实并不高效,由于数组存储是连续的内存空间,所以我们在对数组进行操作时都需要去维护这个连续性,因此也就牺牲了一些效率,当插入或删除数组中元素时数组中元素都需要大量移动如下图所示:

  enter image description here

  在索引为3的位置插入g,需把索引3~n元素后移一位

  enter image description here

  删除数组索引为1的元素,需把索引2~n元素前移一位

  因此数组的插入、删除平均时间复杂度为:O(n),这里说的是平均复杂度是因为还有例外情况,比如在数组末尾插入元素、删除数组末尾元素这些情况时间复杂度为O(1);
  每种编程语言中都存在数组,数组其实还分为静态数组动态数组;静态数组是指数组创建后存储空间固定不变的、而动态数组为在使用数组过程中当存储空间不足时可动态扩容;下面为使用Golang实现的动态数组封装,动态数组的扩容、缩容需要注意扩容的大小与缩容的零界点,此处可能会影响到数组性能;

  type Array struct {
    data []interface{}
    size int
  }

  func NewArray(capacity int) *Array {
    array := new(Array)
    array.data = make([]interface{}, capacity)
    array.size = 0
    return array
  }

  func NewDefaultArray() *Array {
    return NewArray(10)
  }

  /**
  获取元素个数
   */
  func (a *Array) Size() int {
    return a.size
  }

  /**
  获取容量大小
   */
  func (a *Array) Capacity() int {
    return len(a.data)
  }

  /**
  是否为空
   */
  func (a *Array) IsEmpty() bool {
    return a.size == 0
  }

  /**
  往数组末尾添加元素
   */
  func (a *Array) AddLast(e interface{}) error {
    return a.Add(a.size, e)
  }

  /**
  清空数组
   */
  func (a *Array) Clear() {
    a.data = make([]interface{}, a.size)
    a.size = 0
  }

  /**
  往第一个位置添加元素
   */
  func (a *Array) AddFirst(e interface{}) error {
    return a.Add(0, e)
  }

  /**
  往指定索引添加元素
   */
  func (a *Array) Add(index int, e interface{}) error {
if index < 0 || index > a.size {
    return errors.New("Add failed, Require index >= 0 and index< size")
}

if a.size == len(a.data) {
    a.resize(2 * len(a.data))
}

for i := a.size - 1; i >= index; i-- {
    a.data[i+1] = a.data[i]
}
a.data[index] = e
a.size++
return nil
  }

  /**
  更新指定位置元素
   */
  func (a *Array) Update(index int, e interface{}) error {
    if index < 0 || index > a.size {
        return errors.New("update failed, Require index >= 0 and index< size")
    }
    a.data[index] = e
    return nil
  }

  /**
  获取指定位置元素
   */
  func (a *Array) FindElement(index int) interface{} {
    if index < 0 || index > a.size {
        return errors.New("update failed, Require index >= 0 and index< size")
    }
    return a.data[index]
  }

  /**
  删除数组指定索引位置的元素,返回删除的元素
   */
  func (a *Array) Remove(index int) (e interface{}) {
    if index < 0 || index > a.size {
        return errors.New("remove failed, Require index >= 0 and index< size")
    }
    e = a.data[index]
    for i := index + 1; i < a.size; i++ {
        a.data[i-1] = a.data[i]
    }
    a.size--
    //删除元素后数组缩小一位,将该位置元素置nil
    a.data[a.size] = nil
    return
  }

  /**
  删除数组首个元素
   */
  func (a *Array) RemoveFirst() (e interface{}) {
    return a.Remove(0)
  }

  /**
  数组扩容
   */
  func (a *Array) resize(newCapacity int) {
    newData := make([]interface{}, newCapacity)
    for i := 0; i < a.size; i++ {
        newData[i] = a.data[i]
    }
    a.data = newData
  }

参考资料: https://zh.wikipedia.org/wiki/%E6%95%B0%E7%BB%84