数据结构与算法-数组 & 链表

数组是一种常见的线性表结构,它用一组连续的内存空间,来存储一组具有相同类型的数据;定义中标识出来的,是数组的3个基本特性;线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向,除了数组外,链表,队列,栈也都是线性表结构;与它对应的是非线性表结构,如二叉树、堆、图等;

链表也是一种常见的线性表结构,它用一组非连续的内存空间,来存储一组具有相同类型的数据;注意和数组的区别,与数组最大的区别在于,链表是使用一组非连续的内存空间,链表分为单向链表、循环链表、双向链表、双向循环列表;

下面将通过代码实例,来分析这2种数据结构,在查找、插入、删除等常用操作上的区别

一、结构

1、数组的结构
var arr = [5]int64{1,2,8,7,6}
fmt.Printf("%p\n", &arr)
for i,_ := range arr {
   fmt.Printf("第%d元素的内存地址:%p\n", i, &arr[i])
}
输出结果:
0xc000194000
第0元素的内存地址:0xc000194000
第1元素的内存地址:0xc000194008
第2元素的内存地址:0xc000194010
第3元素的内存地址:0xc000194018
第4元素的内存地址:0xc000194020

从上图可以看出,数组的第一个元素的地址就是数组的地址,且内存地址占用8个字节(与定义的int64相关)

2、链表

链表有分为单向链表、双向链表、单向循环、双向循环,又区分有头和无头,一共有8组链表结构,由于无头的链表,在操作上很不简便,且容易出错,而单向链表的删除节点的时间复杂度O(n),这里实现下有头双向链表

package linked

// 定义节点
type Element struct {
   Value interface{}
   prev, next *Element
}
// 前节点
func (e *Element) Next() *Element  {
   if e.next == nil {return nil}
   return e.next
}
// 后节点
func (e *Element) Prev() *Element  {
   if e.prev == nil {return nil}
   return e.prev
}

//定义链表,包括表头、链表长度
type Link struct {
   root Element
   length int
}
func (l *Link)Init() *Link {
   l.root.prev = &l.root
   l.root.next = &l.root
   l.length = 0
   return l
}
func New() *Link { return new(Link).Init() }
func (l *Link)Len() int { return l.length }
func (l *Link)Head() *Element { return &l.root }
func (l *Link)Front() *Element {
   if l.length == 0 {return nil}
   return l.root.next
}
func (l *Link)Back() *Element {
   if l.length == 0 {return nil}
   return l.root.prev
}

func (l *Link)PushFront(v interface{}) *Link {
   e := &Element{v,&l.root, l.root.next}
   l.root.next.prev = e
   l.root.next = e
   l.length++
   return l
}
func (l *Link)PushBack(v interface{}) *Link {
   e := &Element{v,l.root.prev, &l.root}
   l.root.prev.next = e
   l.root.prev = e
   l.length++
   return l
}
func (l *Link)Search(v interface{}) *Element {
   if l.length == 0 {return nil}
   current := l.Front()
   for i := 0; i < l.length; i++ {
      if current.Value == v {
         break
      }
      current = current.Next()
   }
   return current
}
func (l *Link)Find(pos int) *Element {
   if l.length == 0 {return nil}
   if pos < 0 || pos >= l.length {return nil}
   current := l.Front()
   for i := 0; i < l.length; i++ {
      if i == pos {
         break
      }
      current = current.Next()
   }
   return current
}

func (l *Link)InsertBefore(v interface{}, mark *Element) *Element {
   if mark == nil {return nil}
   e := &Element{v,mark.prev, mark}
   mark.prev.next = e
   mark.prev = e
   l.length++
   return e
}

func (l *Link)InsertAfter(v interface{}, mark *Element) *Element {
   if mark == nil {return nil}
   e := &Element{v,mark, mark.next}
   mark.next.prev = e
   mark.next = e
   l.length++
   return e
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>