转载自：http://blog.csdn.net/luoweifu/article/details/8505178

线性表概述

线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性，数据元素可以看成是排列在一条线上或一个环上。

线性表分为静态线性表和动态线性表，常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。

线性表的操作主要包括：

（1）计算表的长度n。

（2）线性表是否为空

（3）将元素添加到线性表的末尾

（4）获取第i个元素，0≤i < n。

（5）清除线性表

（6）返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。

（7）返回列表中最后一次出现指定元素的索引，如果列表不包含此元素，则返回 -1。

（8）将新元素插入第i个位置，0≤i < n，使原来的第i，i+1，…，n–1个元素变为第i+1，i+2，…，n个元素。

（9）更改第i个元素

（10）删除第i个元素，0≤i < n，使原来的第i+1，i+2，…，n–1个元素变为第i，i+1，…，n–2个元素

由此，对线性表抽象数据类型定义List接口如下：

List接口

[java] view plain copy package list;    public interface List {      /**      * 将元素添加到线性表的末尾      */      public void add(Object e);            /**      * 清除线性表      */      public void clear();      /**      * 获取i位置的元素      * @param i      * @return      */      public Object get(int i);      /**      * 返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。      * @param e      * @return      */      public int indexOf(Object e);      /**      * 在i后面插入一个元素e      * @param i      * @param e      */      public void insert(int i, Object e);      /**      * 判断线性表是否为空      * @return      */      public boolean isEmpty();      /**      * 回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回 -1。      * @param e      * @return      */      public int lastIndexOf(Object e);      /**      *  移除列表中指定位置的元素      * @param i      */      public void remove(int i);      /**      * 用指定元素替换列表中指定位置的元素（可选操作）。      * @param i      * @param e      */      public void set(int i, Object e);      /**      * 返回线性表的大小      * @return      */      public int size();  }  

顺序表

结构模型

图顺序存储结构内存结构示意图 

源代码

[java] view plain copy package list;    public class ArrayList implements List{      /**      * 顺序表默认的初始大小      */      public static final int defLen = 10;      private int maxLen;      private Object[] array;      private int size;            public ArrayList() {          size = 0;          maxLen = defLen;          array = new Object[defLen];      }            @Override      public void clear() {          size = 0;      }        @Override      public Object get(int i) {          if(i>=0 && i<size)              return array[i];          else              return null;      }        @Override      public int indexOf(Object e) {          int i =0;           while(i<size && !array[i].equals(e)) {              i++;          }          if(i < size)              return i;          else              return -1;      }        @Override      public void insert(int i, Object e) {          if(i >= size) {              i = size;              if((size) >= maxLen)//如果插入数的位置大于顺序表的最大容量，则扩大容量                  expand();          }          for(int j = size; j>i+1; j--) {              array[j] = array[j-1];          }          array[i+1] = e;          size ++;      }        @Override      public boolean isEmpty() {          if(size == 0)              return true;          else               return false;      }        @Override      public int lastIndexOf(Object e) {          int i = size-1;          while(i>=0 && !array[i].equals(e)) {              i--;          }          if(i>=0)              return i;          else              return -1;      }        @Override      public void remove(int i) {          for(int j=i; j<size-1; j++) {              array[j] = array[j+1];          }          size --;      }        @Override      public void set(int i, Object e) {          array[i] = e;      }        @Override      public int size() {          return size;      }      /**      * 当顺序表的大小不够时，扩充顺序表的大小      */      private void expand() {          maxLen = 2*maxLen;          Object newArray[] = new Object[maxLen];          for(int i=0; i<size; i++) {              newArray[i] = array[i];          }          array = newArray;      }        @Override      public void add(Object e) {          if(size >=maxLen)              expand();          array[size] = e;          size ++;      }  }  

单向循环链表

结构模型

带头结点的单链结构

  (a)空链；  (b)非空链 

源代码

[java] view plain copy package list;  /**  * 链表的结点  * @author luoweifu  *  */  class Node{      Object data;    //数据元素      Node next;      //后驱结点      public Node() {          this(null);      }      public Node(Object data) {          this.data = data;          this.next = null;      }  }  /**  * 带头结点的链式链表,下标从0开始;   * @author Administrator  *  */  public class LinkList implements List {      Node head;  //头结点      int size;   //链表的大小      public LinkList() {          head = new Node();          size = 0;      }      public LinkList(Object[] datas) {          int n = datas.length;          head = new Node();          Node p = head;          for(int i=0; i<n; i++) {              p.next = new Node(datas[i]);              p = p.next;          }          size = n;      }      @Override      public void add(Object e) {          Node p;          if(0 == size) {              p = head;          } else {              p = index(size-1);          }          p.next = new Node(e);          size ++;      }        @Override      public void clear() {          head.next = null;          size = 0;      }        @Override      public Object get(int i) {          Node p = index(i);          return p.data;      }            private Node index(int i) {          Node p = null;          if(i>=0 && i<size){              p = head;              for(int j=0; j<=i; j++) {                  p = p.next;              }          }           return p;      }        @Override      public int indexOf(Object e) {          Node p = head.next;          int i = 0;          while(!p.data.equals(e)) {              p = p.next;              i++;          }          if(i<size)              return i;          else               return -1;      }        @Override      public void insert(int i, Object e) {          Node p = index(i);          Node p2 = new Node(e);          p2.next = p.next;          p.next = p2;          size ++;      }        @Override      public boolean isEmpty() {          if(size ==0)              return true;          else              return false;      }        @Override      public int lastIndexOf(Object e) {          int i = size-1;          while(!get(i).equals(e)) {              i--;          }          if(i>=0)              return i;          else               return -1;      }        @Override      public void remove(int i) {          if(i>=0 && i<size) {              Node p = null;              if(i == 0)                  p = head;              else {                  p = index(i-1);              }              p.next = index(i).next;          }          size --;      }        @Override      public void set(int i, Object e) {          Node p = index(i);          p.data = e;      }        @Override      public int size() {          return size;       }        }  

双向循环链表

结构模型

带头结点的双循环链结构

 (a)空链；  (b)非空链 

源代码

[java] view plain copy package list;  /**  * 链表的结点  * @author luoweifu  *  */  class DlNode{      Object data;      DlNode prior, next;      public DlNode() {          this(null);      }      public DlNode(Object data) {          this.data = data;   //数据元素          this.prior = null;  //前驱结点          this.next = null;   //后驱结点      }  }  /**  * 带头结点的双向循环链表,下标从0开始;   * @author Administrator  *  */  public class DoubleLinkList implements List {      DlNode head;    //头结点      int size;   //链表的大小      public DoubleLinkList() {          head = new DlNode();          head.prior = head;          head.next = head;          size = 0;      }      public DoubleLinkList(Object[] datas) {          int n = datas.length;          head = new DlNode();          DlNode p = head;          DlNode p2 = null;          for(int i=0; i<n; i++) {              p2 = new DlNode(datas[i]);              p.next = p2;              p2.prior = p;              p = p.next;          }          p2.next = head;          head.prior = p2;           size = n;      }      @Override      public void add(Object e) {          DlNode p, p2;          if(0 == size) {              p = head;          } else {              p = index(size-1);          }          p2 = new DlNode(e);          p.next = p2;          p2.prior = p;          p2.next = head;          head.prior = p2;          size ++;      }        @Override      public void clear() {          head.prior = head;          head.next = head;          size = 0;      }        @Override      public Object get(int i) {          DlNode p = index(i);          return p.data;      }            private DlNode index(int i) {          DlNode p = null;          if(i>=0 && i<size){              p = head;              for(int j=0; j<=i; j++) {                  p = p.next;              }          }           return p;      }        @Override      public int indexOf(Object e) {          DlNode p = head.next;          int i = 0;          while(!p.data.equals(e)) {              p = p.next;              i++;          }          if(i<size)              return i;          else               return -1;      }        @Override      public void insert(int i, Object e) {          DlNode p = index(i);          DlNode p2 = new DlNode(e);          p2.next = p.next;          p2.prior = p;          p.next = p2;          size ++;      }        @Override      public boolean isEmpty() {          if(size ==0)              return true;          else              return false;      }        @Override      public int lastIndexOf(Object e) {          DlNode p = head.prior;          int i = size-1;          while(!p.data.equals(e)) {              p = p.prior;              i--;          }          if(i>=0)              return i;          else               return -1;      }        @Override      public void remove(int i) {          if(i>=0 && i<size) {              DlNode p = null;              if(i == 0)                  p = head;              else {                  p = index(i-1);              }              DlNode p2 = index(i).next;              p.next = p2.next;              p2.next.prior = p;          }          size --;      }        @Override      public void set(int i, Object e) {          DlNode p = index(i);          p.data = e;      }        @Override      public int size() {          return size;       }        }  

测试线性表

[java] view plain copy package list;    public class Test {        /**      * 测试线性表      * @param args      */      public static void main(String args[]) {          List list = new ArrayList();          //List list = new LinkList();          //List list = new DoubleLinkList();          for(int i=0; i<10; i++) {              list.add(new Integer(i));          }          list.remove(9);          System.out.print("size;" + list.size() + "\n");          System.out.println("isEmpty:" + list.isEmpty());          System.out.print("第7个位置的元素：" + list.get(7) + "\n");           for(int i=0; i<list.size(); i++) {              System.out.print(list.get(i) + "    ");          }                    list.add(21);          list.add(22);          list.insert(3, new Integer(5));          System.out.print("size:" + list.size() + "\n");          System.out.print("第一次出现5的索引：" + list.indexOf(5) + "\n");          System.out.print("最后一次出现5的索引：" + list.lastIndexOf(5) + "\n");          list.set(0, new Integer(30));          for(int i=0; i<list.size(); i++) {              System.out.print(list.get(i) + "    ");          }      }  }  

结果

size;9 isEmpty:false 第7个位置的元素：7 0    1    2    3    4    5    6    7    8    size:12 第一次出现5的索引：4 最后一次出现5的索引：6 30    1    2    3    5    4    5    6    7    8    21    22