方法和ArrayList的大小问题

作者: 编程技术  发布:2019-09-20

List的接口

 1 func New() *List                                                    //创建List 2 func  Back() *Element                                      //返回List的上一个元素 3 func  Front() *Element                                     //返回List下一个元素 4 func  Init() *List                                         //初始化List 5 func  InsertAfter(v interface{}, mark *Element) *Element   //在指定节点后插入,成功返回插入节点的指针,失败返回nil, 时间复杂度O 6 func  InsertBefore(v interface{}, mark *Element) *Element  //在指定节点之前插入, 成功返回插入节点的指针,失败返回nil, 时间复杂度O 7 func  Len() int                                            //返回链表长度,时间复杂度O 8 func  MoveAfter(e, mark *Element)                          //移动节点e到mark节点之后,时间复杂度O, 处理方式:先删除然后再插入 9 func  MoveBefore(e, mark *Element)                         //移动节点e到mark节点之前,时间复杂度O, 处理方式:先删除然后再插入10 func  MoveToBack(e *Element)                               //移动节点e到链表的尾部11 func  MoveToFront(e *Element)                              //移动节点e到链表的头部12 func  PushBack(v interface{}) *Element                     //在链表尾部追加值为v的新节点13 func  PushBackList(other *List)                            //把链表other所有节点追加到当前链表的尾部14 func  PushFront(v interface{}) *Element                    //在链表的头部插入新节点15 func  PushFrontList(other *List)                           //把链表other所有节点追加到当前链表头部16 func  Remove(e *Element) interface{}                       //删除指定节点

从这些接口我们可以看到Go的list应该是一个双向链表,不然InsertBefore这种操作应该不会放出来。

偶然看到了Collections的copy(List desc,List src)方法.当时就想这个方法和初始化一个List desc=new ArrayList(List c)【参数必须实现Collection接口】的区别。

然后我们再从源码看看List的结构

 1 // Element is an element of a linked list. 2 type Element struct { 3     // Next and previous pointers in the doubly-linked list of elements. 4     // To simplify the implementation, internally a list l is implemented 5     // as a ring, such that &l.root is both the next element of the last 6     // list element  and the previous element of the first list 7     // element ). 8     next, prev *Element 9 10     // The list to which this element belongs.11     list *List12 13     // The value stored with this element.14     Value interface{}15 }

1 // List represents a doubly linked list.2 // The zero value for List is an empty list ready to use.3 type List struct {4     root Element // sentinel list element, only &root, root.prev, and root.next are used5     len  int     // current list length excluding  sentinel element6 }

从这里证实了上面的猜想,这是一个双向链表

两者的差别很大,后者是一个浅拷贝,只是对源list的元素进行拷贝,拷贝的只是引用。拷贝后两个list的元素(引用)不同,但是引用所指向的对 象是一样的。即是两个list的每个元素指向的还是通一内存。然而前者是深拷贝,不光拷贝的是src的元素(引用),src内每个元素的所指向的对象都进 行一次拷贝。即是两个list的每个元素所指向的不是同一内存。

List的使用

 1 package main 2  3 import ( 4     "container/list" 5     "fmt" 6 ) 7  8 func main() { 9 10     list0 := list.New()11     e4 := list0.PushBack(4)12     e1 := list0.PushFront(1)13     list0.InsertBefore(3, e4)14     list0.InsertAfter(2, e1)15 16     for e := list0.Front(); e != nil; e = e.Next() {17         fmt.Print(e.Value, " ")18     }19     fmt.Println("r")20 21     front := list0.Front()22     back := list0.Back()23 24     fmt.Println("front is:", front.Value)25     fmt.Println("back is:", back.Value)26     fmt.Println("length is", list0.Len27 28     list0.InsertBefore(0, front)29     list0.InsertAfter(5, back)30 31     list0.PushFront(-1)32     list0.PushBack(6)33     for e := list0.Front(); e != nil; e = e.Next() {34         fmt.Print(e.Value, " ")35     }36     fmt.Println("r")37     list0.Remove(list0.Front38     for e := list0.Front(); e != nil; e = e.Next() {39         fmt.Print(e.Value, " ")40     }41 42     fmt.Println("r")43     list1 := list.New()44     list1.PushBack(7)45     list1.PushBack(8)46     list0.PushBackList47     for e := list0.Front(); e != nil; e = e.Next() {48         fmt.Print(e.Value, " ")49     }50     fmt.Println("r")51 }

10-14行往list写入1,2,3,4

16行遍历打印list

21-16行打印front 和back节点

42-48行把另一个list追加到list的back

运行结果是:

1 2 3 4 front is: 1back is: 4length is 4-1 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 

使用后者进行拷贝的结果是:当你的desc链表发生改变时,src也将会随之改变。
使用前者进行拷贝时你又必须要注意目标链表的长度必须要比源链表的长度大或者相等。

举例如下:
List src1=new ArrayList(3)
src1.add("a");
src2.add("b");
src3.add("c");

如果你使用下面方法copy链表
/*******************************/
List des1=new ArrayList(3);
Collections.copy(des1,src1);
/*******************************/
将会出错,抛出数组越界异常。
当时我怎么想都想不明白为什么,明明已经设置了长度为3,为什么还会出错!
后来打印出des1.size()才知道des1的长度为0;3表示的是这个List的容纳能力为3,并不是说des1中就有了3个元素。查看api才知 道,它的capacity(容纳能力大小)可以指定(最好指定)。而初始化时size的大小永远默认为0,只有在进行add和remove等相关操作 时,size的大小才变化。然而进行copy()时候,首先做的是将desc1的size和src1的size大小进行比较,只有当desc1的size 大于或者等于src1的size时才进行拷贝,否则抛出IndexOutOfBoundsException异常。

所以可以通过下面的方法指定目标desc的大小
/*******************************/
List des1=new ArrayList(Arrays.asList(new object[src1.size]));//注意:new ArrayList(Collection col)参数必须要实现Collection 接口。
Collections.copy(des1,src1);
/*******************************/
执行第一句后size的大小是3,其实它是对一个空数组的浅拷贝。

本文由贝博体育app发布于编程技术,转载请注明出处:方法和ArrayList的大小问题

关键词:

上一篇:没有了
下一篇:没有了