- packagelinked;
- public classLinkedList<E> {
- // 定义内部类, 该类代表节点, 用于存放对象数据, 以及下一个节点数据 // 下一个数据, 其实不应该理解为指向的数据, 更应该理解为递归包含数据 private classNode{
- publicE e;
- publicNode next;
- publicNode(E e,Node next){
- this.e=e;
- this.next=next;
- }
- publicNode(E e){
- this(e,null);
- }
- publicNode(){
- this(null,null);
- }
- }
- // 虚拟头节点, 不存放任何元素, 方便处理链表的第一个元素 (真正的头节点) 时与处理其他元素无异 privateNode dummyHead;
- private intsize;
- // 链表的构造函数 publicLinkedList(){
- dummyHead= newNode(null,null);
- size= 0;
- }
- // 获取链表中元素的个数 public intgetSize(){
- returnsize;
- }
- // 判断链表是否为空 public booleanisEmpty(){
- returnsize==0;
- }
- // 在指定位置加入节点 public voidadd(intindex,E e){
- if(index <0 || index> size){
- throw newIllegalArgumentException("add failed.index is illegal.");
- }
- // 找到欲加入位置的前一个节点 Node prev = dummyHead;
- for(inti=0;i<index;i++){
- prev = prev.next;
- }
- // 插入节点, 相当于两步操作, index 前一个节点的 next 指向新的节点, 创建的新的节点的 next 指向原 index 位置的节点 prev.next= newNode(e,prev.next);
- // 新增或者删除节点都需要改变链表的 sizesize++;
- }
- // 在链表头部加入节点, 链表的第一个真正含有数据的元素是从 0 开始算的 public voidaddFirst(E e){
- add(0,e);
- }
- // 在链表的尾部加入节点(si 既代表链表元素的个数, 也代表待插入元素的位置)public voidaddLast(E e){
- add(size,e);
- }
- // 获取第 index 位置的节点中的元素数据 publicE get(intindex){
- // 注意此处如果 index 等于 size 也是不合法的, 因为 size 是指向待插入元素的位置 if(index <0 || index>= size){
- throw newIllegalArgumentException("add failed.index is illegal.");
- }
- Node current = dummyHead;
- // 如果 index==0, 则需要遍历一次, 从 dummyHead 指向第一个 Node, 如果 index==1, 则需要遍历两次, 才能指向 1 位置的元素, 依次类推 // 所以此处判断条件要用<=indexfor(inti=0;i<=index;i++){
- current = current.next;
- }
- // 直接用 current.e, 这也是 Node 中属性 E 设置为 public 访问范围的原因 returncurrent.e;
- }
- // 获取链表的第一个元素 publicE getFist(){
- returnget(0);
- }
- // 获取链表的最后一个元素 publicE getLast(){
- returnget(size-1);
- }
- // 修改链表第 index 位置的元素 public voidset(intindex,E e){
- // 注意此处如果 index 等于 size 也是不合法的, 因为 size 是指向待插入元素的位置, 逻辑与查找 index 位置的逻辑相同 if(index <0 || index>= size){
- throw newIllegalArgumentException("add failed.index is illegal.");
- }
- Node current = dummyHead;
- for(inti=0;i<=index;i++){
- current = current.next;
- }
- current.e= e;
- }
- // 查找链表中是否有元素 epublic booleancontains(E e){
- Node current = dummyHead;
- // 遍历链表的第一种方式 /*for(int i=0;i<size;i++){
- current =current.next;
- if(e.equals(current.e)){
- return true;
- }
- }*/
- // 遍历链表的第二种方式 while(current.next!= null){
- current = current.next;
- if(e.equals(current.e)){
- return true;
- }
- }
- return false;
- }
- // 删除指定索引位置的元素 publicE remove(intindex){
- if(index <0 || index>= size){
- throw newIllegalArgumentException("add failed.index is illegal.");
- }
- Node prev = dummyHead;
- for(inti=0;i<index;i++){
- prev = prev.next;
- }
- Node indexNode = prev.next;
- // 通过下边的两步断开索引的前后连接 //1 索引位置前一个 node 的 next 不再指向索引位置的元素, 而是指向索引的下一个元素 prev.next= indexNode.next;
- //2 将原索引位置的下一个元素设置为 nullindexNode.next= null;
- size--;
- returnindexNode.e;
- }
- // 删除链表中的第一个元素 publicE removeFirst(){
- returnremove(0);
- }
- // 删除链表中的最后一个元素 publicE removeLost(){
- returnremove(size-1);
- }
- @Override
- publicString toString() {
- StringBuilder sb = newStringBuilder();
- sb.append(String.format("LinkedList: size = %d\n",size));
- Node current = dummyHead;
- for(inti=0;i<size;i++){
- current = current.next;
- sb.append(current.e);
- if(current.next!= null){
- sb.append("->");
- }
- }
- returnsb.toString();
- }
- public static voidmain(String[] args) {
- LinkedList<Integer> linkedList = newLinkedList<>();
- for(inti=0;i<8;i++){
- linkedList.addLast(i);
- System.out.println(linkedList);
- }
- linkedList.add(5,9);
- System.out.println(linkedList);
- linkedList.remove(6);
- System.out.println(linkedList);
- linkedList.removeFirst();
- System.out.println(linkedList);
- linkedList.removeLost();
- System.out.println(linkedList);
- }
- }
来源: http://www.bubuko.com/infodetail-3351412.html