文档介绍:Java数据结构—链表学****目标链表的概念单链表双链表数组是很有用的数据结构,但是有两个局限:若改变数据的大小就需要创建一个新数组并从原数组中拷贝所有数据至新数组;数组数据在内存中依次连续存储,向数组中插入一项要移动数组中其他数据。数组的缺点链表这种数据结构是使用指针(即引用)将存储数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点,因而在插入或者删除时不再需要移动元素来腾出空间或填补空缺。需要作出的改变就是在每个单元中设置指针来表示表中元素之间的逻辑关系(前还是后)。因此每个单元至少有两个域,一个用于数据元素的存储,一个用于指向其他单元的指针。这种具有一个数据域和多个指针域的存储单元称为节点(Node)。链表的概念链表的图示node(节点)节点本身就是对象数据指针节点接口publicinterfaceNode{//获取节点数据域publicObjectgetData();//设置节点数据域publicvoidsetData(Objectobj);}节点的设计单链表单链表的每个节点只有一个指向表中下一个节点的指针。第一个节点称为首节点,最后一个称为尾节点。尾节点的特征是next引用为空(null)。nodenodea0nexta1next单链表节点的设计除了需要实现Node接口定义的获取和设置数据域的两个方法以外,还需要提供对指向下一节点的指针的操作方法。为此提供两个方法,getNext()和setNext(Nodenode)。lassSinglyLinkedNodeimplementsNode{ privateObjectobj; privateSinglyLinkedNodenext;单链表节点的设计(续)publicSinglyLinkedNode(){ this(null,null); } publicSinglyLinkedNode(Objectobj,SinglyLinkedNodenext){ =obj; =next; }单链表节点的设计(续)publicSinglyLinkedNodegetNext(){ returnnext; } publicvoidsetNext(SinglyLinkedNodenext){ =next; } publicObjectgetData(){ returnobj; } publicvoidsetData(Objectobj){ =obj; }}