1.实现线性表的方式：
1)数组(arrray):数组大小是固定的。如果元数个数超过了数组的容量，就创建一个更大的数组，并将当前数组的元素复制到新数组中。
2)链式结构(linked structure):链式结构是由节点组成，每个节点都是动态创建的。用来储存一个元素。所有的节点链接成一个线性表。
{*}设计指南：通用的操作可以归纳为一个接口或一个抽象类。一个好的策略就是在设计中提供接口和便利抽象类，以整合抽象类和接口的优点。抽象类提供了接口的骨架实现，可以更有效的实现接口。
我们把这样的接口命名为MyList,把便利类命名为MyAbtractList.
下面是MyList的源代码
1 package List_24; 2 3 import java.util.Collection; 4 5 public interface $24_01MyList<E> extends Collection<E> { 6 /** Add a new element at the specified index in this list */ 7 public void add(int index, E e); 8 9 /** Return the element from this list at the specified index */ 10 public E get(int index); 11 12 /** 13 * Return the index of the first matching element in this list. Return -1 if no 14 * match. 15 */ 16 public int indexOf(Object e); 17 18 /** 19 * Return the index of the last matching element in this list Return -1 if no 20 * match. 21 */ 22 public int lastIndexOf(E e); 23 24 /** 25 * Remove the element at the specified position in this list Shift any 26 * subsequent elements to the left. Return the element that was removed from the 27 * list. 28 */ 29 public E remove(int index); 30 31 /** 32 * Replace the element at the specified position in this list with the specified 33 * element and returns the new set. 34 */ 35 public E set(int index, E e); 36 37 @Override /** Add a new element at the end of this list */ 38 public default boolean add(E e) { 39 add(size(), e); 40 return true; 41 } 42 43 @Override /** Return true if this list contains no elements */ 44 public default boolean isEmpty() { 45 return size() == 0; 46 } 47 48 @Override /** 49 * Remove the first occurrence of the element e from this list. Shift any 50 * subsequent elements to the left. Return true if the element is removed. 51 */ 52 public default boolean remove(Object e) { 53 if (indexOf(e) >= 0) { 54 remove(indexOf(e)); 55 return true; 56 } else 57 return false; 58 } 59 60 @Override 61 public default boolean containsAll(Collection<?> c) { 62 // Left as an exercise 63 return true; 64 } 65 66 @Override 67 public default boolean addAll(Collection<? extends E> c) { 68 // Left as an exercise 69 return true; 70 } 71 72 @Override 73 public default boolean removeAll(Collection<?> c) { 74 // Left as an exercise 75 return true; 76 } 77 78 @Override 79 public default boolean retainAll(Collection<?> c) { 80 // Left as an exercise 81 return true; 82 } 83 84 @Override 85 public default Object[] toArray() { 86 // Left as an exercise 87 return null; 88 } 89 90 @Override 91 public default <T> T[] toArray(T[] array) { 92 // Left as an exercise 93 return null; 94 } 95 }
下面是MyAstractList的源代码
1 package List_24; 2 3 public abstract class $24_02MyAbstractList<E> implements $24_01MyList<E> { 4 protected int size = 0; // The size of the list 5 6 /** Create a default list */ 7 protected $24_02MyAbstractList() { 8 } 9 10 /** Create a list from an array of objects */ 11 protected $24_02MyAbstractList(E[] objects) { 12 for (int i = 0; i < objects.length; i++) 13 add(objects[i]); 14 } 15 16 @Override /** Add a new element at the end of this list */ 17 public void add(E e) { 18 add(size, e); 19 } 20 21 @Override /** Return true if this list contains no elements */ 22 public boolean isEmpty() { 23 return size == 0; 24 } 25 26 @Override /** Return the number of elements in this list */ 27 public int size() { 28 return size; 29 } 30 31 @Override /** 32 * Remove the first occurrence of the element e from this list. Shift any 33 * subsequent elements to the left. Return true if the element is removed. 34 */ 35 public boolean remove(E e) { 36 if (indexOf(e) >= 0) { 37 remove(indexOf(e)); 38 return true; 39 } else 40 return false; 41 } 42 }
{*}数组线性表采用数组来实现
{*}该数据数组的类型是E[]类型，所以数组中每个元素实际储存的时对象的引用
下面是TestArrayList的源代码
1 package List_24; 2 3 public class $24_04TestArrayList { 4 public static void main(String[] args) { 5 // Create a list 6 $24_03MyArrayList<String> list = new $24_03MyArrayList<>(); 7 8 // Add elements to the list 9 list.add("America"); // Add it to the list 10 System.out.println("(1) " + list); 11 12 list.add(0, "Canada"); // Add it to the beginning of the list 13 System.out.println("(2) " + list); 14 15 // Add elements to the list 16 list.add("Russia"); // Add it to the end of the list 17 System.out.println("(3) " + list); 18 19 // Add elements to the list 20 list.add("France"); // Add it to the end of the list 21 System.out.println("(4) " + list); 22 23 list.add(2, "Germany"); // Add it to the list at index 2 24 System.out.println("(5) " + list); 25 26 list.add(5, "Germany"); // Add it to the list at index 5 27 System.out.println("(6) " + list); 28 29 //Remove elements from the list 30 list.remove("Canada");//Same sa list.remove(0) in this case 31 System.out.println("(7) " + list); 32 33 list.remove(2);//Remove the element at index 2 34 System.out.println("(8) " + list); 35 36 list.remove(list.size()-1);//Remove the last element 37 System.out.print("(9) "+list+"n(10) "); 38 39 for(String s:list) { 40 System.out.print(s.toUpperCase()+" "); 41 } 42 } 43 }
{*}链表采用链接结构实现
当需要移动大量元素时数组实现的线性表效率很低，这种情况下采用链式结构来实现线性表。
链表中的每个元素都包含一个成为节点的结构。当向链表中加入一个新的元素时，就会产生一个包含它的节点。每个节点都和它的相邻节点相链接。
节点可以按如下定义为一个类：
1 class Node<E> { 2 E element; 3 Node<E> next; 4 5 public Node(E e) { 6 element = e; 7 } 8 }
在这里，变量head指向线性表的第一个节点，而变量tail指向最后一个节点。如果线性表为空，这两个线性表均为null。
例子：创建一个储存三个结点的链表，每个节点储存一个字符串元素。
步骤一：声明head和tail
Node<String> head=null;
Node<String> tail=null;
步骤二：
创建第一个节点并将它追加到线性表中
head=new Node<>("Chicago");
tail=head;
步骤三：
创建第二个节点并将它追加到线性表中
tail.next=new Node<>("Denver");
tail=tail.next;
步骤四：
创建第三个节点并将它追加到线性表中
tail.next=new Node<>("Dallas");
tail=tail.next;
每个节点都包含元素和一个名为next的数据域，next指向下一个元素。如果节点是线性表的最后一个，那么它的指针数据域next所包含的值是null.可以使用这个特性来检测某节点是否是最后节点。
例如：下面代码可用来遍历线性表的所有节点
Node current = head; while(current != null){ System.out.println(current.element); current = current.next(); }
MyLinkList类使用链式结构实现动态线性表，它继承自MyAbstractList类。
假设已经实现了这个类，下面给出该类的测试程序。
1 package List_24; 2 3 public class $24_05TestMyLinkedList { 4 /** Main method */ 5 public static void main(String[] args) { 6 // Create a list for strings 7 $24_06MyLinkedList<String> list = new $24_06MyLinkedList<>(); 8 9 // Add elements to the list 10 list.add("America"); // Add it to the list 11 System.out.println("(1) " + list); 12 13 list.add(0, "Canada"); // Add it to the beginning of the list 14 System.out.println("(2) " + list); 15 16 list.add("Russia"); // Add it to the end of the list 17 System.out.println("(3) " + list); 18 19 list.addLast("France"); // Add it to the end of the list 20 System.out.println("(4) " + list); 21 22 list.add(2, "Germany"); // Add it to the list at index 2 23 System.out.println("(5) " + list); 24 25 list.add(5, "Norway"); // Add it to the list at index 5 26 System.out.println("(6) " + list); 27 28 list.add(0, "Poland"); // Same as list.addFirst("Poland") 29 System.out.println("(7) " + list); 30 31 // Remove elements from the list 32 list.remove(0); // Same as list.remove("Australia") in this case 33 System.out.println("(8) " + list); 34 35 list.remove(2); // Remove the element at index 2 36 System.out.println("(9) " + list); 37 38 list.remove(list.size() - 1); // Remove the last element 39 System.out.print("(10) " + list + "n(11) "); 40 41 for (String s : list) 42 System.out.print(s.toUpperCase() + " "); 43 44 list.clear(); 45 System.out.println("nAfter clearing the list, the list size is " + list.size()); 46 } 47 }
下面提供该类的具体实现。
1 package List_24; 2 3 public class $24_06MyLinkedList<E> extends $24_02MyAbstractList<E> { 4 private Node<E> head, tail; 5 private int size = 0; // Number of elements in the list 6 7 /** Create an empty list */ 8 public $24_06MyLinkedList() { 9 } 10 11 /** Create a list from an array of objects */ 12 public $24_06MyLinkedList(E[] objects) { 13 for (int i = 0; i < objects.length; i++) 14 add(objects[i]); 15 } 16 17 /** Return the head element in the list */ 18 public E getFirst() { 19 if (size == 0) { 20 return null; 21 } else { 22 return head.element; 23 } 24 } 25 26 /** Return the last element in the list */ 27 public E getLast() { 28 if (size == 0) { 29 return null; 30 } else { 31 return tail.element; 32 } 33 } 34 35 /** Add an element to the beginning of the list */ 36 public void addFirst(E e) { 37 Node<E> newNode = new Node<>(e); // Create a new node 38 newNode.next = head; // link the new node with the head 39 head = newNode; // head points to the new node 40 size++; // Increase list size 41 42 if (tail == null) // the new node is the only node in list 43 tail = head; 44 } 45 46 /** Add an element to the end of the list */ 47 public void addLast(E e) { 48 Node<E> newNode = new Node<>(e); // Create a new for element e 49 50 if (tail == null) { 51 head = tail = newNode; // The new node is the only node in list 52 } else { 53 tail.next = newNode; // Link the new with the last node 54 tail = newNode; // tail now points to the last node 55 } 56 57 size++; // Increase size 58 } 59 60 @Override /** 61 * Add a new element at the specified index in this list. The index of the head 62 * element is 0 63 */ 64 public void add(int index, E e) { 65 if (index == 0) { 66 addFirst(e); 67 } else if (index >= size) { 68 addLast(e); 69 } else { 70 Node<E> current = head; 71 for (int i = 1; i < index; i++) { 72 current = current.next; 73 } 74 Node<E> temp = current.next; 75 current.next = new Node<>(e); 76 (current.next).next = temp; 77 size++; 78 } 79 } 80 81 /** 82 * Remove the head node and return the object that is contained in the removed 83 * node. 84 */ 85 public E removeFirst() { 86 if (size == 0) { 87 return null; 88 } else { 89 E temp = head.element; 90 head = head.next; 91 size--; 92 if (head == null) { 93 tail = null; 94 } 95&
登录查看全部
参与评论
手机查看
返回顶部