Java数据结构链表.ppt
Java数据结构链表,学习目标,链表的概念单链表双链表,数组的缺点,数组是很有用的数据结构，但是有两个局限：若改变数据的大小就需要创建一个新数组并从原数组中拷贝所有数据至新数组；数组数据在内存中依次连续存储，向数组中插入一项要移动数组中其他数据。,链表的概念,链表这种数据结构是使用指针(即引用)将存储数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在插入或者删除时不再需要移动元素来腾出空间或填补空缺。需要作出的改变就是在每个单元中设置指针来表示表中元素之间的逻辑关系(前还是后)。因此每个单元至少有两个域，一个用于数据元素的存储，一个用于指向其他单元的指针。这种具有一个数据域和多个指针域的存储单元称为节点(Node)。,链表的图示,node(节点),节点本身就是对象,节点的设计,节点接口public interface Node/获取节点数据域public Object getData();/设置节点数据域public void setData(Object obj);,单链表,单链表的每个节点只有一个指向表中下一个节点的指针。第一个节点称为首节点，最后一个称为尾节点。尾节点的特征是next引用为空(null)。,node,node,单链表节点的设计,除了需要实现Node接口定义的获取和设置数据域的两个方法以外，还需要提供对指向下一节点的指针的操作方法。为此提供两个方法，getNext()和setNext(Node node)。public class SinglyLinkedNode implements Node private Object obj;private SinglyLinkedNode next;,单链表节点的设计(续),public SinglyLinkedNode()this(null,null);public SinglyLinkedNode(Object obj,SinglyLinkedNode next)this.obj=obj;this.next=next;,单链表节点的设计(续),public SinglyLinkedNode getNext()return next;public void setNext(SinglyLinkedNode next)this.next=next;public Object getData()return obj;public void setData(Object obj)this.obj=obj;,单链表的设计,单链表的一个重要特性是只能通过前驱节点找到后续节点，而无法从后续节点找到前驱节点。因此在单链表中进行查找操作，只能从链表的首节点开始，通过每个节点的next引用来依次访问链表中的每个节点以完成相应的查找操作。为使程序更简洁，通常在单链表的最前面添加一个哑元节点，也称为头节点(Head)，注意，有别于真正的首节点，头节点中不存储任何实质的数据对象，其next通常指向0位的元素。,单链表的设计(续),通用的单链表类的初始化public class SinglyLinkedList/头节点private SinglyLinkedNode head;/元素个数private int size;public SinglyLinkedList()head=new SinglyLinkedNode();/为什么新建了SinglyLinkedNode类的对象，size还设为0?size=0;,单链表的设计(续),通用的单链表类的查找方法给定索引，返回节点public Object get(int index)throws IndexOutOfBoundsException if(size()=0)/添加size()方法return null;else if(index=size()throw new IndexOutOfBoundsException();else SinglyLinkedNode node=head.getNext();for(;index 0;index-)node=node.getNext();return node.getData();,单链表的设计(续),通用的单链表类的查找方法给定对象，返回索引public int indexOf(Object obj)SinglyLinkedNode node=head.getNext();int index=0;while(node!=null)if(node.getData().equals(obj)return index;elseindex+;node=node.getNext();return-1;/如果没找到，返回-1,练习,请设计并实现操作单链表的方法：判断单链表结构中是否包含指定对象public boolean contains(Object obj),单链表的设计(续),对于任何基于序号的插入、删除，以及任何基于数据元素所在节点的前面或后面的插入、删除，在带头节点的单链表中均可转化为在某个特定节点之后完成节点的插入、删除，而不用考虑插入、删除是在链表的首部、中间还是尾部等不同情况。,练习,请设计并实现操作单链表的方法：将指定数据元素插入到链表尾部public void add(Object o)将指定数据元素插入到链表中指定位置public void add(int index,Object o)删除链表中指定位置的数据元素public boolean remove(int index)删除链表中第一次出现的指定数据元素public boolean remove(Object o),双链表,双向链表是对单链表的扩充，以弥补单链表只能访问后续节点而不方便访问前驱节点的缺憾。双向链表的结构是在单链表的节点结构上新增加一个域，用来指向直接前驱节点。,双向链表的图示,next,prev,node,node,node,节点,双链表节点的设计,除了需要实现Node接口定义的获取和设置数据域的两个方法以外，还需要提供对指向上下节点的指针的操作方法。为此提供四个方法，getNext()、setNext(Node node)、getPre()、setPre(Node node)public class DLinkedNode implements Node private Object obj;private DLinkedNode next;private DLinkedNode pre;,双链表节点的设计(续),public DLinkedNode()this(null,null,null);public DLinkedNode(Object obj,DLinkedNode pre,DLinkedNode next)this.obj=obj;this.pre=pre;this.next=next;,双链表节点的设计(续),public DLinkedNode getPre()return pre;public void setPre(DLinkedNode pre)this.pre=pre;public DLinkedNode getNext()return next;public void setNext(DLinkedNode next)this.next=next;public Object getData()return obj;public void setData(Object obj)this.obj=obj;,双链表的设计,在双链表中进行查找、删除、插入操作，即能从链表的首节点开始，也能从尾部开始，时间花费和单链表相比不占优势，但是为使程序更简洁，通常在双链表的最前面和最后面各添加一个哑元节点。这样，由于首尾节点的存在，插入、删除操作都可被看作在双向链表中间某个节点的插入、删除；并且因为首尾节点的存在，整个链表永远不会为空，因此在插入和删除节点之后，也不用考虑链表由空变为非空或由非空变为空的情况下head和tail的指向问题，从而简化了问题。,双链表的设计(续),通用的双链表类的初始化public class DLinkedList/头节点private DLinkedNode head;/头节点private DLinkedNode tail;/元素个数private int size;public DLinkedList()head=new DLinkedNode();tail=new DLinkedNode();head.setNext(tail);tail.setPre(head);size=0;,双链表的设计(续),对边界条件的检测protected DLinkedNode check(Node p)throws Exceptionif(p=null)throw new Exception(“节点为空！”);if(p=head)throw new Exception(“节点不能指向头节点！”);if(p=tail)throw new Exception(“节点不能指向尾节点！”);DLinkedNode node=(DLinkedNode)p;return node;,双链表的设计(续),演示一个方法的实现把给定对象作为第一个元素插入链表public void addFirst(Object o)DLinkedNode node=new DLinkedNode(o,head,head.getNext();head.getNext().setPre(node);head.setNext(node);size+;请设计将给定对象插入到尾部的方法public void addLast(Object o),双链表的设计(续),public void addLast(Object o)DLinkedNode node=new DLinkedNode(o,tail.getPre(),tail);tail.getPre().setNext(node);tail.setPre(node);size+;请设计方法移除指定元素public void remove(Node p),双链表的设计(续),public void remove(Node p)throws ExceptionDLinkedNode node=check(p);node.getPre().setNext(node.getNext();node.getNext().setPre(node.getPre();size-;请设计方法移除尾部元素public void removeLast(),双链表的设计(续),请设计方法移除指定位置的元素public void remove(int index)请设计方法将链表中指定位置元素替换为指定的元素，并返回以前在指定位置处的元素public void set(int index,Object obj),链表的使用,可以使用链表替代数组实现栈和队列。public class StackLinkedList private SinglyLinkedNode top;/指向栈顶元素private int size;/栈中元素数目public StackLinkedList()top=null;size=0;public int getSize()return size;public boolean isEmpty()return(top=null)?true:false;,链表的使用,public Object peek()if(isEmpty()return null;return top.getData();public Object pop()if(isEmpty()return null;Object o=top.getData();top=top.getNext();size-;return o;,链表的使用,public void push(Object o)SinglyLinkedNode n=new SinglyLinkedNode(o,top);top=n;size+;,练习,使用DLinkedList实现栈和队列。使用java.util.LinkedList实现栈和队列。,
