链表:逻辑上连续,多个节点采用挂载的方式进行连接,物理上不连续.链表分为单链表和双链表.
一丶单链表
①链表的实现(增删改查):
// 1、无头单向非循环链表实现
public class SingleLinkedList {//头插法public void addFirst(int val){//尾插法
}public void addLast(int val){//任意位置插入,第一个数据节点为0号下标}public boolean addIndex(int index,int data){//查找是否包含关键字key是否在单链表当中}public boolean contains(int key){//删除第一次出现关键字为key的节点}public void remove(int key){//删除所有值为key的节点}public void removeAllKey(int key){}}②创建节点 :
class Node {int val;Node next;public Node(int val) {this.val = val;}
}具体代码实现:
package singallink;public class SingalLinkedList {private int size;private Node head;public void addFirst(int val) {Node node = new Node(val);if(head == null){head = node;}else{node.next = head;head = node;}size++;}public void addIndex(int index,int val){if(index < 0 || index > size){System.out.println("add index illegal");return;}if(index == 0){addFirst(val);return;}Node node = new Node(val);Node prev = head;for (int i = 0; i < index - 1; i++) {prev = prev.next;}node.next = prev.next;prev.next = node;size++;}public void addLast(int val){addIndex(size,val);}public int seek(int index){if(rangeCheck(index)){Node node = head;for (int i = 0; i < index; i++) {node = node.next;}return node.val;}else{System.out.println("get index illegal");return -1;}}public boolean contains(int val){for (Node i = head; i != null; i=i.next) {if(i.val == val){return true;}}return false;}public int modify(int index,int newVal){if(rangeCheck(index)){Node node = head;for (int i = 0; i < index; i++) {node = node.next;}int oldVal = node.val;node.val = newVal;return oldVal;}else{System.out.println("modify index illegal");return -1;}}public void removeIndex(int index){if(rangeCheck(index)){if(index == 0){Node temp = head;head = head.next;temp.next = null;size--;}Node prev = head;for (int i = 0; i < index; i++) {prev = prev.next;}Node cur = prev.next;prev.next = cur.next;cur.next = null;size--;}else{System.out.println("remove index illegal!");}}public void removeFirst(){removeIndex(0);}public void removeLast(){removeIndex(size-1);}public void removeValOnce(int val){if(rangeCheck(val)){if(head != null && head.val == val){Node temp = head;head = head.next;temp.next = null;size--;}else{Node prev = head;while(prev.next != null){if(prev.next.val == val){Node cur = prev.next;prev.next = cur.next;cur.next = null;size--;return;}prev = prev.next;}}}}public void removeValAll(int val){while(head != null && head.val == val){head = head.next;size--;}if(head == null){return;}else{Node prev = head;while(prev.next != null){if(prev.next.val == val){Node cur = prev.next;prev.next = cur.next;cur.next = null;size--;}else{prev = prev.next;}}}}public boolean rangeCheck(int index){if(index < 0 || index >= size){return false;}return true;}public String toString(){String ret = "";Node node = head;while(node != null){ret+=node.val;ret+="->";node = node.next;}ret+="END";return ret;}
}class Node {int val;Node next;public Node(int val) {this.val = val;}
}二丶双链表
①链表的实现:
public class DoubleLinkedList {//头插法public void addFirst(int val){}//尾插法public void addLast(int val){}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int val){}//查找值val是否在双链表当中public boolean contains(int val){}//删除第一次出现值为val的节点public void remove(int val){}//删除所有值为val的节点public void removeAllval(int val){}}②构造节点
class Node{Node prev;int val;Node next;public Node(int val) {this.val = val;}public Node(Node prev, int val, Node next) {this.prev = prev;this.val = val;this.next = next;}
}具体代码实现:
package doublelink;public class DoubleLinkedList {private Node head;private int size;private Node tail;public void addFirst(int val){Node node = new Node(null,val,head);if(head == null){tail = node;}else{head.prev = node;}head = node;size++;}public void addLast(int val){Node node = new Node(tail,val,null);if(tail == null){head = node;}else{tail.next = node;}tail = node;size++;}public void addIndex(int index,int val){if(index < 0 ||index > size){System.out.println("add index illegal!");}else if(index == 0){addFirst(val);}else if(index == size){addLast(val);}else{Node prev = node(index - 1);Node newNode = new Node(prev,val,prev.next);prev.next.prev = newNode;prev.next = newNode;size++;}}public int get(int index){if(rangeCheck(index)){return node(index).val;}else{System.out.println("get index illegal!");return -1;}}private Node node (int index){Node ret = null;if(index < (size << 1)){ret = head;for (int i = 0; i < index; i++) {ret = ret .next;}}else{ret = tail;for (int i = size-1; i > index; i--) {ret = ret.prev;}}return ret;}public boolean contains(int val){for(Node x = head;x != null;x = x.next){if(x.val == val){return true;}}return false;}public int set(int index,int newVal){if(rangeCheck(index)){Node node = node(index);int oldVal = node.val;node.val = newVal;return oldVal;}else{System.err.println("set index illegal!");return -1;}}public void remove(int index){if(rangeCheck(index)){Node node = node(index);unlink(node);}else{System.out.println("remove index illegal!");}}public void removeValOnce(int val){for(Node x = head;x != null;x=x.next){if(x.val == val){unlink(x);break;}}
}public void removeValAll(int val){for(Node x = head;x != null;){if(x.val == val){Node next = x.next;unlink(x);x = next;}else{x = x.next;}}}private void unlink(Node node){Node prev = node.prev;Node next = node.next;if(prev == null){head = next;}else{prev.next = node.next;node.prev = null;}if(next == null){tail = node.prev;}else{next.prev = prev;node.next = null;}size--;}public boolean rangeCheck(int index){if(index < 0 || index >= size){return false;}else{return true;}}public String toString(){String ret = "";Node node = head;while(node != null){ret += node.val + "->";node = node.next;}ret += "END";return ret;}
}class Node{Node prev;int val;Node next;public Node(int val) {this.val = val;}public Node(Node prev, int val, Node next) {this.prev = prev;this.val = val;this.next = next;}
}