1 public class Demo { 2 public static void main(String[] args) { 3 MyLinkList linkList = new MyLinkList(); 4 // 添加 5 linkList.add("123"); 6 linkList.add("aaa"); 7 linkList.add("中国人"); 8 System.out.println("获取第0个元素:" + linkList.getNode(0)); 9 System.out.println("打印全部链表元素:" + linkList); 10 // 添加到最前 11 linkList.addFirst("ccc"); 12 System.out.println("在最前面添加ccc之后打印链表元素:" + linkList); 13 // 添加到最后 14 linkList.addLast("zzz"); 15 System.out.println("在最后面添加zzz之后打印链表元素:" + linkList); 16 // 添加到指定位置 17 linkList.add(4, "ggg"); 18 System.out.println("在第4个位置添加ggg之后打印链表元素:" + linkList); 19 // 移除最前的 20 linkList.removeFirst(); 21 System.out.println("移除最前面的元素之后打印链表元素:" + linkList); 22 // 移除最后的 23 linkList.removeLast(); 24 System.out.println("移除最后面的元素之后打印链表元素:" + linkList); 25 // 移除指定位置上的 26 linkList.remove(2); 27 System.out.println("移除第二个位置上的元素之后打印链表元素:" + linkList); 28 // 返回指定位置上的元素 29 System.out.println("返回第一个位置上的元素:" + linkList.getNode(1)); 30 System.out.println("完成所有操作之后打印链表元素:" + linkList); 31 } 32 } 33 class MyLinkList implements MyMethod { 34 // 头节点 35 private Node head = new Node(null); 36 // 链表大小 37 private int size; 38 @Override 39 public boolean add(int index, String data) { 40 if (index < 0 || index >= getSize()) { 41 throw new IndexOutOfBoundsException("数组下标越界!"); 42 } else { 43 addBefore(new Node(data), getNode(index)); 44 return true; 45 } 46 } 47 @Override 48 public boolean add(String data) { 49 return addLast(data); 50 } 51 @Override 52 public boolean addFirst(String data) { 53 addAfter(new Node(data), head); 54 return true; 55 } 56 @Override 57 public boolean addLast(String data) { 58 addBefore(new Node(data), head); 59 return true; 60 } 61 @Override 62 public Node getNode(int index) { 63 if (index < 0 || index >= size) 64 throw new IndexOutOfBoundsException("数组下标越界!"); 65 Node node = head.next; 66 for (int i = 0; i < index; i++) 67 node = node.next; 68 return node; 69 } 70 @Override 71 public int getSize() { 72 return size; 73 } 74 @Override 75 public boolean remove(int index) { 76 if (index < 0 || index >= size) 77 throw new IndexOutOfBoundsException("数组下标越界!"); 78 removeNode(getNode(index)); 79 return true; 80 } 81 @Override 82 public boolean removeFirst() { 83 removeNode(head.next); 84 return true; 85 } 86 @Override 87 public boolean removeLast() { 88 removeNode(head.prev); 89 return false; 90 } 91 // 在指定节点的前一个节点进行插入 92 private void addBefore(Node newNode, Node node) { 93 // 要添加节点的下一个节点为指定节点 94 newNode.next = node; 95 // 要添加节点的前一个节点为指定节点的前一个 96 newNode.prev = node.prev; 97 // 要添加节点的下一个节点的前一个节点为要添加的节点 98 newNode.next.prev = newNode; 99 // 要添加节点的前一个节点的下一个节点为要添加的节点 100 newNode.prev.next = newNode; 101 // 长度自增 102 size++; 103 } 104 // 在指定节点的后一个节点进行插入 105 private void addAfter(Node newNode, Node node) { 106 // 要添加节点的前一个节点为指定节点 107 newNode.prev = node; 108 // 要添加节点的下一个节点为指定节点的下一个 109 newNode.next = node.next; 110 // 要添加节点的下一个节点的前一个节点为要添加的节点 111 newNode.next.prev = newNode; 112 // 要添加节点的前一个节点的下一个节点为要添加的节点 113 newNode.prev.next = newNode; 114 // 长度自增 115 size++; 116 } 117 // 删除节点 118 private void removeNode(Node removeNode) { 119 // 要删除节点的写一个节点的前一个节点为要删除节点的前一个节点 120 removeNode.next.prev = removeNode.prev; 121 // 要删除节点的前一个节点的下一个节点为要删除节点的下一个节点 122 removeNode.prev.next = removeNode.next; 123 // 要删除节点的下一个节点为null 124 removeNode.next = null; 125 // 要删除节点的前一个节点为null 126 removeNode.prev = null; 127 size--; 128 } 129 class Node { 130 private String data; 131 private Node prev = this; 132 private Node next = this; 133 public Node(String data) { 134 this.data = data; 135 } 136 @Override 137 public String toString() { 138 return data; 139 } 140 } 141 @Override 142 public String toString() { 143 StringBuffer sb = new StringBuffer(); 144 Node node = head; 145 for (int i = 0; i < size; i++) { 146 node = node.next; 147 if (i > 0) 148 sb.append(","); 149 sb.append(node.data); 150 } 151 return sb.toString(); 152 } 153 } 154 interface MyMethod { 155 // 添加元素 156 public boolean add(String data); 157 // 添加元素到最前面 158 public boolean addFirst(String data); 159 // 添加元素到最后面 160 public boolean addLast(String data); 161 // 在指定位置添加元素 162 public boolean add(int index, String data); 163 // 移除最前面的元素 164 public boolean removeFirst(); 165 // 移除最后面的元素 166 public boolean removeLast(); 167 // 移除指定位置上的元素 168 public boolean remove(int index); 169 // 获取指定位置上的元素 170 public Node getNode(int index); 171 // 获取链表的长度 172 public int getSize(); 173 }
执行结果:
1 获取第0个元素:123 2 打印全部链表元素:123,aaa,中国人 3 在最前面添加ccc之后打印链表元素:ccc,123,aaa,中国人 4 在最后面添加zzz之后打印链表元素:ccc,123,aaa,中国人,zzz 5 在第4个位置添加ggg之后打印链表元素:ccc,123,aaa,中国人,ggg,zzz 6 移除最前面的元素之后打印链表元素:123,aaa,中国人,ggg,zzz 7 移除最后面的元素之后打印链表元素:123,aaa,中国人,ggg 8 移除第二个位置上的元素之后打印链表元素:123,aaa,ggg 9 返回第一个位置上的元素:aaa 10 完成所有操作之后打印链表元素:123,aaa,ggg