• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

链表详解(易懂)

java 来源:Tupac.Amaru.Shakur 7次浏览
  • 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点(node)。
  • 链表的第一个节点和最后一个节点,分别称为链表的头节点和尾节点。尾节点的特征是其 next 引用为空(null)。链表中每个节点的 next 引用都相当于一个指针,指向另一个节点,借助这些 next 引用,我们可以从链表的头节点移动到尾节点。
  • 链表数据结构中主要包含单向链表、双向链表及循环链表:
  1. 单向链表
      单向链表只有一个指针域,在整个节点中数据域用来存储数据元素,指针域用于指向下一个具有相同结构的节点。


      单向链表中,每个节点的数据域都是通过一个 Object 类的对象引用来指向数据元素的,与数组类似,单向链表中的节点也具有一个线性次序,即如果节点 a1 的 next 引用指向节点 a2,则 a1 就是 a2 的直接前驱,a2 是 a1 的直接后续。只能通过前驱节点找到后续节点,而无法从后续节点找到前驱节点。
    特点:
      数据元素的存储对应的是不连续的存储空间,每个存储结点对应一个需要存储的数据元素。每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。
      逻辑上相邻的节点物理上不必相邻。
    缺点:
    1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。
    2、查找结点时链式存储要比顺序存储慢(每个节点地址不连续、无规律,导致按照索引查询效率低下)。
    优点:
    1、插入、删除灵活 (不必移动节点,只要改变节点中的指针,但是需要先定位到元素上)。
    2、有元素才会分配结点空间,不会有闲置的结点。

  2. 双向链表
      要在单向链表中找到某个节点的前驱节点,必须从链表的头节点出发依次向后寻找,但是需要Ο(n)时间。为此我们可以扩展单向链表的节点结构,使得通过一个节点的引用,不但能够访问其后续节点,也可以方便的访问其前驱节点。扩展单向链表节点结构的方法是,在单链表节点结构中新增加一个域,该域用于指向节点的直接前驱节点。该链表称为双向链表。单向链表只能从一个方向遍历,双向链表可以从两个方向遍历。


      在使用双向链表实现链接表时,为使编程更加简洁,我们使用带两个哑元节点的双向链表来实现链接表。其中一个是头节点,另一个是尾节点,它们都不存放数据元素,头节点的pre 为空,而尾节点的 Next 为空。

      在具有头尾节点的双向链表中插入和删除节点,无论插入和删除的节点位置在何处,因为首尾节点的存在,插入、删除操作都可以被归结为某个中间节点的插入和删除;并且因为首尾节点的存在,整个链表永远不会为空,因此在插入和删除节点之后,也不用考虑链表由空变为非空或由非空变为空的情况下 head 和 tail 的指向问题;从而简化了程序。

  3. 循环链表
      头节点和尾节点被连接在一起的链表称为循环链表,这种方式在单向和双向链表中皆可实现。循环链表中第一个节点之前就是最后一个节点,反之亦然。

简单用双向列表模拟一下LinkedList,Java代码如下:

public class Node {//节点类
        private Object previous;//每个节点的前一个指向
        private Object obj;//每个节点中间位置用来存放你存储的东西
        private Object next;//每个节点的后一个指向
        public Object getPrevious() {
                return previous;
        }
        public void setPrevious(Object previous) {
                this.previous = previous;
        }
        public Object getObj() {
                return obj;
        }
        public void setObj(Object obj) {
                this.obj = obj;
        }
        public Object getNext() {
                return next;
        }
        public void setNext(Object next) {
                this.next = next;
        }
}
public class MyLinkedList {//模拟LinkedList
        //对于每一个LinkedList集合,都有一个首节点和一个尾节点:
        private Node first;//首节点
        private Node last;//尾节点 
        
        
        public void add(Object obj){
                if(first==null){	//证明我放入的是第一个节点
                        //创建一个独立的节点:
                        Node n=new Node();
                        n.setPrevious(null);
                        n.setObj(obj);
                        n.setNext(null);
                        
                        //将我想象的这个链中的首节点,位节点都设置为n
                        first=n;
                        last=n;
                }else{	//放入的是第二个节点,第三个节点。。。。。
                        //创建一个独立的节点:
                        Node n=new Node();
                        n.setPrevious(last);
                        n.setObj(obj);
                        n.setNext(null);
                        
                        //将链表的最后一个的下一个指向为n
                        last.setNext(n);
                        
                        //将链表的最后一个指向n
                        last=n;
                }
        }
        
        public static void main(String[] args) {
                MyLinkedList list=new MyLinkedList();
                list.add("java");
                list.add("css");
                list.add("solr");
                list.add("jsp");
                
                System.out.println("结束");
  
        }
     
}


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)