文档章节

链表详述

liddblog
 liddblog
发布于 2017/01/11 23:13
字数 1903
阅读 4
收藏 1

链接点(Link)

       在链表中,每个数据项都被包含在“链接点”(Link)中。一个链接点是某个类的对象,这个类一般叫做Link,因为一个链表中,有许多类似的链接点,所以有必要用一个不同于链表的类来表达链接点,每个Link对象中都包含一个对下一个链接点引用的字段,(通常叫做next)。但是链表(LinkList)本身的对象中有一个字段指向对第一个链接点的引用。
       链表不同于数组的主要特点之一是,在一个数组中每一项占用一个特定的位置,这个位置可以用一个下标号直接访问,它就像一排房子,你可以凭地址找到其中特定的一间,在链表中,寻找一个特定的元素的唯一方法就是沿着这个元素一直向下寻找,不能直接访问到数据,必须使用数据之间的关系来定位它,你从第一项开始,到第二项,然后到第二项,到第三项,知道发现要找的那个数据项。

单链表

利用面向对象的方法实现的单链表的java代码

//Link类
//此类中的iData和dData是一个节点中存储的数据,在实际应用中并非是这样的,
//可以是多个数据,或者是存储一个对象如这样:
//class Link
//   {
//   public Person person;          //data item
//   public Link next;              // next link in list
//   }
//数据类型可以是私有的,当设置成私有时,必须添加set和get方法
class Link
   {
   public int iData;              // data item
   public double dData;           // data item
   public Link next;              // next link in list
// -------------------------------------------------------------
   public Link(int id, double dd) // constructor
      {
      iData = id;                 // initialize data
      dData = dd;                 // ('next' is automatically
      }                           //  set to null)
// -------------------------------------------------------------
   public void displayLink()      // display ourself
      {
      System.out.print("{" + iData + ", " + dData + "} ");
      }
   }  // end class Link

//LinkList类
class LinkList
   {
   private Link first;            // ref to first link on list

// -------------------------------------------------------------
   public LinkList()              // constructor
      {
      first = null;               // no links on list yet
      }
// -------------------------------------------------------------
   public boolean isEmpty()       // true if list is empty
      {
      return (first==null);
      }
// -------------------------------------------------------------
                                  // insert at start of list
   public void insertFirst(int id, double dd)
      {                           // make new link
      Link newLink = new Link(id, dd);
      newLink.next = first;       // newLink --> old first
      first = newLink;            // first --> newLink
      }
// -------------------------------------------------------------
   public Link deleteFirst()      // delete first item
      {                           // (assumes list not empty)
      Link temp = first;          // save reference to link
      first = first.next;         // delete it: first-->old next
      return temp;                // return deleted link
      }
// -------------------------------------------------------------
//查找指定位置的节点
   public Link find(int key)      // find link with given key
      {                           // (assumes non-empty list)
      Link current = first;              // start at 'first'
      while(current.iData != key)        // while no match,
         {
         if(current.next == null)        // if end of list,
            return null;                 // didn't find it
         else                            // not end of list,
            current = current.next;      // go to next link
         }
      return current;                    // found it
      }
// -------------------------------------------------------------
//删除指定位置的节点
   public Link delete(int key)    // delete link with given key
      {                           // (assumes non-empty list)
      Link current = first;              // search for link
      Link previous = first;
      while(current.iData != key)
         {
         if(current.next == null)
            return null;                 // didn't find it
         else
            {
            previous = current;          // go to next link
            current = current.next;
            }
         }                               // found it
      if(current == first)               // if first link,
         first = first.next;             //    change first
      else                               // otherwise,
         previous.next = current.next;   //    bypass it
      return current;
      }
// -------------------------------------------------------------
   public void displayList()
      {
      System.out.print("List (first-->last): ");
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink();   // print data
         current = current.next;  // move to next link
         }
      System.out.println("");
      }
// -------------------------------------------------------------
   }  // end class LinkList
////////////////////////////////////////////////////////////////
class LinkListApp
   {
   public static void main(String[] args)
      {
      LinkList theList = new LinkList();  // make new list

      theList.insertFirst(22, 2.99);      // insert four items
      theList.insertFirst(44, 4.99);
      theList.insertFirst(66, 6.99);
      theList.insertFirst(88, 8.99);

      theList.displayList();              // display list

      while( !theList.isEmpty() )         // until it's empty,
         {
         Link aLink = theList.deleteFirst();   // delete link
         System.out.print("Deleted ");         // display it
         aLink.displayLink();
         System.out.println("");
         }
      theList.displayList();              // display list
      }  // end main()
   }  // end class LinkListApp

其他方法

       上述代码已经提供可在表头插入和删除节点的方法,以及查找和删除一个指定链接点的方法,还可以在想象其他的有用的方法,比如,insertAfter()可以查找一个含有特定关键字的链接点,然后再他后面插入一个新的链接点。后续的笔记中写迭代器的时候,应该会看到这样的方法。

双端链表

       双端链表与传统的链表非常相似,但是他有一个新增的特性,即对最后一个链接点的引用,就像对第一个链接点的引用一样,对最后一个链接点的引用允许像在表头一样,在表尾直接插入一个链接点,当然,仍然可以在蒲绒的单链表的表尾插入一个链接点,方法时遍历整个链表直到到达表尾,但是这种方法效率很低,像访问表头一样访问表尾的特性,使双端链表更适合与一些普通链表不方便操作的场合,队列的实现就是这样一个情况,顺表提一句,不要把双端链表和双向链表搞混,他们是不一样的。

双端链表实现的java代码

// firstLastList.java
// demonstrates list with first and last references
// to run this program: C>java FirstLastApp
////////////////////////////////////////////////////////////////
class Link
   {
   public long dData;                 // data item
   public Link next;                  // next link in list
// -------------------------------------------------------------
   public Link(long d)                // constructor
      { dData = d; }
// -------------------------------------------------------------
   public void displayLink()          // display this link
      { System.out.print(dData + " "); }
// -------------------------------------------------------------
   }  // end class Link
////////////////////////////////////////////////////////////////
class FirstLastList
   {
   private Link first;               // ref to first link
   private Link last;                // ref to last link
// -------------------------------------------------------------
   public FirstLastList()            // constructor
      {
      first = null;                  // no links on list yet
      last = null;
      }
// -------------------------------------------------------------
   public boolean isEmpty()          // true if no links
      { return first==null; }
// -------------------------------------------------------------
   public void insertFirst(long dd)  // insert at front of list
      {
      Link newLink = new Link(dd);   // make new link

      if( isEmpty() )                // if empty list,
         last = newLink;             // newLink <-- last
      newLink.next = first;          // newLink --> old first
      first = newLink;               // first --> newLink
      }
// -------------------------------------------------------------
   public void insertLast(long dd)   // insert at end of list
      {
      Link newLink = new Link(dd);   // make new link
      if( isEmpty() )                // if empty list,
         first = newLink;            // first --> newLink
      else
         last.next = newLink;        // old last --> newLink
      last = newLink;                // newLink <-- last
      }
// -------------------------------------------------------------
   public long deleteFirst()         // delete first link
      {                              // (assumes non-empty list)
      long temp = first.dData;
      if(first.next == null)         // if only one item
         last = null;                // null <-- last
      first = first.next;            // first --> old next
      return temp;
      }
// -------------------------------------------------------------
   public void displayList()
      {
      System.out.print("List (first-->last): ");
      Link current = first;          // start at beginning
      while(current != null)         // until end of list,
         {
         current.displayLink();      // print data
         current = current.next;     // move to next link
         }
      System.out.println("");
      }
// -------------------------------------------------------------
   }  // end class FirstLastList
////////////////////////////////////////////////////////////////
class FirstLastApp
   {
   public static void main(String[] args)
      {                              // make a new list
      FirstLastList theList = new FirstLastList();

      theList.insertFirst(22);       // insert at front
      theList.insertFirst(44);
      theList.insertFirst(66);

      theList.insertLast(11);        // insert at rear
      theList.insertLast(33);
      theList.insertLast(55);

      theList.displayList();         // display the list

      theList.deleteFirst();         // delete first two items
      theList.deleteFirst();

      theList.displayList();         // display again
      }  // end main()
   }  // end class FirstLastApp

注意:双端链表插入和删除方法和普通链表相应部分类似,然而,两个插入方法都要考虑一种特殊情况,即插入前链表是空的,不幸的是,用双端链表也不能有助于删除最后一个链接点,因为没有一个引用指向倒数第二个链接点,如果最后一个链接点被删除,倒数第二个链接点的next字段应该变成null值,为了方便的删除最后一个链接点,需要一个双向链表,后续后写笔记。(当然也可以遍历整个链表找到最后一个链接点,但是那样做效率不高)。

链表的效率

       在表头插入和删除速度很快,仅需要改变一两个引用值,所以花费O(1)的时间。平均起来,查找,删除和在指定链接点后面插入都需要搜索链表中的一半链接点,需要O(N)次比较,在数组中执行这些操作也需要O(N)次比较,但是链表仍然要快一些,因为当插入和删除链接点时,链表不需要移动任何东西,增加的效率是很显著的,特别是当复制时间远远大于比较时间的时候。
       当然,链表比数组优越的另外一个重要的方面是链表需要多少内存就可以用多少内存,并且可以扩展到所有可用内存,数组的大小在他创建的时候就固定了,所以经常由于数组太大导致效率低下,或者数组太小导致空间溢出,向量是一种可扩展的数组,它可以通过可变长度解决这个问题,但是他经常只允许以固定的大小增量扩展(例如快要溢出的时候,就增加一倍数组容量),这个解决方案在内存使用效率上来说还是要比聊表的低。

© 著作权归作者所有

liddblog
粉丝 4
博文 70
码字总数 65593
作品 0
海淀
程序员
私信 提问
学习JavaScript数据结构和算法(第二版) 读后感

总体概述 本书是由[巴西] 格罗纳(Loiane Groner)[著作],全书总共238页; 本书从介绍javascript语言入手,然后分别介绍了数组(列表)、栈、队列、链表等顺序数据结构,然后依次介绍了集合、...

张蕾_
2018/06/01
0
0
Netty源码—六、tiny、small内存分配

tiny内存分配 tiny内存分配流程: 如果申请的是tiny类型,会先从tiny缓存中尝试分配,如果缓存分配成功则返回 否则从tinySubpagePools中尝试分配 如果上面没有分配成功则使用allocateNormal进...

lacker
2018/07/28
0
0
图的搜索

前言 图的搜索指的是系统化地跟随图中的边来访问图中每一个结点,并不是随意地访问图中的结点。图的搜索算法可以用来发现图的结构,许多图的算法都要求先搜索全图,可以说,图的搜索是整个图...

某昆
2017/09/16
0
0
PHP哈希表碰撞攻击原理

文章出处:http://www.codinglabs.org/html/hash-collisions-attack-on-php.html 最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招。本文结合P...

鉴客
2012/04/17
1K
0
浅谈php的哈希碰撞

hash table在php中由为重要。存储变量的'符号表',array和object存储的数据结构,执行上下文的变量及函数均使用哈希表结构存储。 Hash,简单来讲,是一种将任意长度的输入变换成固定长度的输...

stone_
2016/07/13
44
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot 2 实战:使用 Spring Boot Admin 监控你的应用

1. 前言 生产上对 Web 应用 的监控是十分必要的。我们可以近乎实时来对应用的健康、性能等其他指标进行监控来及时应对一些突发情况。避免一些故障的发生。对于 Spring Boot 应用来说我们可以...

码农小胖哥
今天
6
0
ZetCode 教程翻译计划正式启动 | ApacheCN

原文:ZetCode 协议:CC BY-NC-SA 4.0 欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 学习资源 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 ...

ApacheCN_飞龙
今天
4
0
CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
今天
7
0
从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
7
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部