数组是一种常见的线性表结构,它用一组连续的内存空间,来存储一组具有相同类型的数据;定义中标识出来的,是数组的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 }