一、单向链表
单向链表的普通实现
Java实现:
package linkedlist;
/**
* 单向链表的普通实现
*
* @param <E> E
* @author ZZX
*/
public class SinglyLinkedList<E> implements LinkedList<E> {
/**
* 节点内部类
*/
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
/**
* 虚拟头节点，避免逻辑上区别处理头部节点
*/
private Node dummyHead;
private int size;
public SinglyLinkedList() {
dummyHead = new Node();
size = 0;
}
public boolean add(int index, E e) {
if (index < 0 || index > size) {
return false;
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
prev.next = new Node(e, prev.next);
size++;
return true;
}
public E findFirst() {
return dummyHead.next.e;
}
public void addFirst(E e) {
// Node node = new Node(e);
// node.next = head;
// head = node;
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
public E get(int index) {
return getNode(index).next.e;
}
public void set(int index, E e) {
getNode(index).next.e = e;
}
public boolean contains(E e) {
Node curNode = dummyHead.next;
while (curNode != null) {
if (e.equals(curNode.e)) {
return true;
}
curNode = curNode.next;
}
return false;
}
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("非法index");
}
Node prevNode = getNode(index);
Node retNode = prevNode.next;
prevNode.next = retNode.next;
retNode.next = null;
size--;
return retNode.e;
}
private Node getNode(int index) {
Node prevNode = dummyHead;
for (int i = 0; i < index; i++) {
prevNode = prevNode.next;
}
return prevNode;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("LinkedList: [");
Node curNode = dummyHead.next;
while (curNode != null) {
sb.append(curNode.e + "-->");
curNode = curNode.next;
}
sb.append("Null]");
return sb.toString();
}
}
Kotlin实现：
//ToDo
单向链表的递归实现
Java实现:
package linkedlist;
import javafx.util.Pair;
/**
* 单向链表的递归实现
*
* @param <E> E
* @author ZZX
*/
public class SinglyLinkedList<E> implements LinkedList<E> {
/**
* 节点内部类
*/
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head;
private int size;
public SinglyLinkedList() {
head = null;
size = 0;
}
public boolean add(int index, E e) {
if (index < 0 || index > size) {
return false;
}
head = add(head, index, e);
size++;
return true;
}
private Node add(Node node, int index, E e) {
if (0 == index) {
return new Node(e, node);
}
node.next = add(node.next, index - 1, e);
return node;
}
public void addFirst(E e) {
add(0, e);
}
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("非法Index");
}
return get(head, index);
}
public E get(Node node, int index) {
if (0 == index) {
return node.e;
}
return get(node.next, index - 1);
}
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("非法Index");
}
set(head, index, e);
}
private void set(Node node, int index, E e) {
if (0 == index) {
node.e = e;
return;
}
set(node.next, index - 1, e);
}
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("非法Index");
}
Pair<Node, E> res = remove(head, index);
return res.getValue();
}
private Pair<Node, E> remove(Node node, int index) {
if (0 == index) {
return new Pair<>(node.next, node.e);
}
Pair<Node, E> res = remove(node.next, index - 1);
node.next = res.getKey();
return new Pair<>(node, res.getValue());
}
public E findFirst() {
return head.next.e;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node curNode = head;
while (curNode != null) {
sb.append(curNode).append("-->");
curNode = curNode.next;
}
return sb.append("NULL").toString();
}
public static void main(String[] args) {
SinglyLinkedList<Integer> singlyLinkedList = new SinglyLinkedList<>();
for (int i = 0; i < 10; i++) {
singlyLinkedList.addFirst(i);
}
System.out.println(singlyLinkedList);
singlyLinkedList.remove(2);
System.out.println(singlyLinkedList);
singlyLinkedList.set(3, 129384);
System.out.println(singlyLinkedList);
System.out.println(singlyLinkedList.get(3));
}
}
二、双向链表
Java实现：
//ToDo
Kotlin实现:
//TODO
三、循环链表
Java实现：
//ToDo
Kotlin实现:
//TODO
- Tips：Java/Kotlin链表接口
//Java
package linkedlist;
/**
* 链表增删改查接口
* @author ZhuZongxing
* @param <E> 泛型
*/
public interface LinkedList<E> {
boolean add(int index, E e);
E remove(int index);
void set(int index, E e);
E get(int index);
int getSize();
boolean isEmpty();
}
网友评论