Java数据结构之线性表

Java数据结构之线性表完整攻略

什么是线性表

线性表是n个数据元素的有限序列，其中数据元素的类型相同。线性表中含有首元素和末元素。若表中只有一个数据元素，则该数据元素既是首元素又是末元素，这个数据元素成为线性表的唯一元素。

线性表的基本操作

• 初始化操作 initList(List L)：建立一个空的线性表L
• 插入操作 insert(List L, int i, Object o)：将元素o插入到线性表L的第i个位置
• 删除操作 delete(List L, int i)：删除线性表L的第i个元素
• 查找操作 getElement(List L, int i)：返回线性表L中第i个元素的值
• 求线性表长度 getListLength(List L)：返回线性表L的长度
• 清空操作 clearList(List L)：清空线性表L中的所有元素

线性表的顺序存储结构

线性表的顺序存储结构可以使用数组来实现。定义一个数组L来存放线性表的数据元素，同时定义一个变量length来记录线性表的长度。

例如，下面的示例代码演示了使用Java数组来实现一个线性表：

public class ArrayList {

   private int[] list;
   private int length;

   public ArrayList(int capacity) {
      this.list = new int[capacity];
      this.length = 0;
   }

   public void insert(int index, int value) {
      if (index < 0 || index > length) {
         throw new IndexOutOfBoundsException("Index out of range!");
      }
      if (length == list.length) {
         int[] newList = new int[list.length * 2];
         for (int i = 0; i < length; i++) {
            newList[i] = list[i];
         }
         list = newList;
      }
      for (int i = length; i > index; i--) {
         list[i] = list[i - 1];
      }
      list[index] = value;
      length++;
   }

   public void delete(int index) {
      if (index < 0 || index >= length) {
         throw new IndexOutOfBoundsException("Index out of range!");
      }
      for (int i = index; i < length - 1; i++) {
         list[i] = list[i + 1];
      }
      length--;
   }

   public int getElement(int index) {
      if (index < 0 || index >= length) {
         throw new IndexOutOfBoundsException("Index out of range!");
      }
      return list[index];
   }

   public int getListLength() {
      return length;
   }

   public boolean isEmpty() {
      return length == 0;
   }

   public void clear() {
      length = 0;
   }

   public static void main(String[] args) {
      ArrayList list = new ArrayList(5);
      list.insert(0, 1);
      list.insert(1, 2);
      list.insert(2, 3);
      list.insert(1, 4);
      list.delete(2);
      System.out.println("List length: " + list.getListLength());
      for (int i = 0; i < list.getListLength(); i++) {
         System.out.println("Index " + i + ": " + list.getElement(i));
      }
   }
}

线性表的链式存储结构

线性表的链式存储结构使用链表来实现。每个节点存储数据元素，同时还需要一个指向下一个节点的指针。

例如，下面的示例代码演示了使用Java链表来实现一个线性表：

public class LinkedList {

   private Node head;
   private int length;

   private class Node {
      int data;
      Node next;

      Node(int data) {
         this.data = data;
      }
   }

   public LinkedList() {
      this.head = null;
      this.length = 0;
   }

   public void insert(int index, int value) {
      if (index < 0 || index > length) {
         throw new IndexOutOfBoundsException("Index out of range!");
      }
      Node node = new Node(value);
      if (index == 0) {
         node.next = head;
         head = node;
      } else {
         Node prev = findNode(index - 1);
         node.next = prev.next;
         prev.next = node;
      }
      length++;
   }

   public void delete(int index) {
      if (index < 0 || index >= length) {
         throw new IndexOutOfBoundsException("Index out of range!");
      }
      if (index == 0) {
         head = head.next;
      } else {
         Node prev = findNode(index - 1);
         prev.next = prev.next.next;
      }
      length--;
   }

   public int getElement(int index) {
      if (index < 0 || index >= length) {
         throw new IndexOutOfBoundsException("Index out of range!");
      }
      Node node = findNode(index);
      return node.data;
   }

   public int getListLength() {
      return length;
   }

   public boolean isEmpty() {
      return length == 0;
   }

   public void clear() {
      head = null;
      length = 0;
   }

   private Node findNode(int index) {
      Node node = head;
      for (int i = 0; i < index; i++) {
         node = node.next;
      }
      return node;
   }

   public static void main(String[] args) {
      LinkedList list = new LinkedList();
      list.insert(0, 1);
      list.insert(1, 2);
      list.insert(2, 3);
      list.insert(1, 4);
      list.delete(2);
      System.out.println("List length: " + list.getListLength());
      for (int i = 0; i < list.getListLength(); i++) {
         System.out.println("Index " + i + ": " + list.getElement(i));
      }
   }
}

以上代码演示了如何在Java中使用数组和链表来实现线性表的基本操作，具体实现可以根据实际需求进行调整。